python - 有效地生成所有小于 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”弹出递归，或者只是从递归函数中掉出来。

谢谢你的智慧!

附加说明:

我现在确实有一种方法可以做到这一点:我编写了一个函数来分解数字，因此我可以将它们分解为素数，并产生结果。没问题。我依靠缓存“数字 N 的最低素因数是什么”来保持这种速度非常快...... N 高达 1000 万。

但是，一旦我从缓存中取出，我们就会将其转变为“幼稚”的因式分解。 (呸。)

这篇文章的重点是:

我假设“从它们的因子生成大型复合物”将比“分解大型复合物”更快......尤其是因为我不关心顺序，并且

如何让 Python 生成器“递归”调用自身，并生成生成的单个流？

最佳答案

假设 primesiter(n) 在所有素数上创建一个迭代器，直到 n(1 不应该包含在 primesiter 中，或者下面的代码进入信息循环)

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)

输出

>> 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)，并且我使用了列表而不是元组。如果需要，两者都可以轻松解决，但我会将其留作练习。

关于python - 有效地生成所有小于 N 的合数(及其因式分解)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10109510/