高效生成所有小于 N 的合数（及其因式分解）

我想构建一个高效的 Python 迭代器/生成器，它会产生：

• 所有小于 N 的合数
• 连同他们的质因数分解

我将其称为“composites_with_factors()”

假设我们已经有小于 N 的素数列表，或者可以执行相同操作的素数生成器。

请注意，我：

• 不需要按数字顺序生成数字
• 不关心一开始是否产生 1
• 不关心素数是否也产生

我认为这可以通过一个聪明的递归生成器来完成......

因此，例如，调用composites_with_factors(16) 可能会产生：

# yields values in form of "composite_value, (factor_tuple)"
2, (2)
4, (2, 2)
8, (2, 2, 2)
6, (2, 3)
12, (2, 2, 3)
10, (2, 5)
14, (2, 7)
3, (3)
9, (3, 3)
15, (3, 5)
5, (5)
7, (7)
11, (11)
13, (13)

正如您从我的输出顺序中看到的那样，我的设想是从可用素数生成器上的最小素数开始，输出该素数小于 N 的所有幂，然后再次尝试该素数的幂，但在每个阶段都会看看我是否可以应用额外素数的幂（并且仍然小于 N）。当与该素数的所有组合完成后，将其丢弃，并使用素数生成器上可用的下一个最低素数重复。

我尝试使用“递归生成器”来执行此操作，这让我非常困惑何时使用“yield”、“raise StopIteration”或“return”退出递归，或者干脆退出递归函数。

感谢您的智慧！

附加说明：

I do现在有一种方法可以做到这一点：我已经编写了一个对数字进行因式分解的函数，因此我可以将它们分解为素数，并产生结果。没问题。我依靠“数字 N 的最低质因数是多少”的缓存来保持速度非常快......对于 N 高达 1000 万。

然而，一旦我脱离了缓存，我们就会将其转变为“天真的”保理。 （恶心。）

这篇文章的要点是：

• 我假设“从它们的因子生成大型复合材料”将比“分解大型复合材料”更快......特别是因为我不关心顺序，并且
• 如何让 Python 生成器“递归地”调用自身，并生成单个生成内容流？

假设primesiter(n)在所有素数上创建一个迭代器，直到n（1 不应包含在primesiter，或者在下面的代码中输入 inf。环形）

def composite_value(n, min_p = 0):
    for p in primesiter(n):
        # avoid double solutions such as (6, [2,3]), and (6, [3,2])
        if p < min_p: continue
        yield (p, [p])
        for t, r in composite_value(n//p, min_p = p): # uses integer division
            yield (t*p, [p] + r)

Output

>> list(composite_value(16))
[(2, [2]),
 (4, [2, 2]),
 (8, [2, 2, 2]),
 (16, [2, 2, 2, 2]),
 (12, [2, 2, 3]),
 (6, [2, 3]),
 (10, [2, 5]),
 (14, [2, 7]),
 (3, [3]),
 (9, [3, 3]),
 (15, [3, 5]),
 (5, [5]),
 (7, [7]),
 (11, [11]),
 (13, [13])]

注意：它还包括 n (= 16)，并且我使用列表而不是元组。如果需要的话，这两个问题都可以轻松解决，但我将把它留作练习。