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

Question

我想构建一个高效的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生成器“递归”调用自身并产生单个生成的流？

- Dan H

---

你对这个方法做了哪些努力？请展示你的代码。 - Makoto

你已经制作了质数生成器，还是只是从奇数开始的生成器？也许一次只做一部分会更容易理解。请展示你目前为止所拥有的代码。 - gbulmer

@DanH：这是一个起点。如果你把你目前的进展发出来，也许我们中的某个人可以更好地了解你如何解决问题。不要害羞，展示你所做的和它的外观。 - Makoto

你提到想要递归地实现这个，但是使用筛法难以被超越！可以参考维基百科上的埃拉托色尼筛法进行简单修改以保留因子。 - Hooked

@Hooked：好的，我可以再看一下筛法。也许我可以“反转”它以产生合数而不是质数。然而，我曾经尝试过实现一个筛法（用于质数），在我的观察中，它占用了大量的内存（因为每个阶段都需要“记住”它要过滤掉什么）。 - Dan H

Answer 1

假设 primesiter(n) 创建了一个迭代器，可以列出所有小于n的质数（primesiter不应包括1，否则会导致以下代码进入无限循环）。

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

- catchmeifyoutry

---

太棒了！这就是我一直找不到的“递归生成器”。让我感到困惑的地方有两个：a）在函数的单个调用中需要两个“for循环”，b）在“内部for循环”之前需要一个yield，在“内部for循环”中需要另一个yield。 - Dan H

Answer 2

以下是基于筛法的实现（请原谅不太Pythonic的代码 :)）:

def sieve(n):
    # start each number off with an empty list of factors
    #   note that nums[n] will give the factors of n
    nums = [[] for x in range(n)]
    # start the counter at the first prime
    prime = 2
    while prime < n:
        power = prime
        while power < n:
            multiple = power
            while multiple < n:
                nums[multiple].append(prime)
                multiple += power
            power *= prime
        # find the next prime
        #   the next number with no factors
        k = prime + 1
        if k >= n:    # no primes left!!!
            return nums
        # the prime will have an empty list of factors
        while len(nums[k]) > 0:
            k += 1
            if k >= n:    # no primes left!!!
                return nums
        prime = k
    return nums


def runTests():
    primes = sieve(100)
    if primes[3] == [3]:
        print "passed"
    else:
        print "failed"
    if primes[10] == [2,5]:
        print "passed"
    else:
        print "failed"
    if primes[32] == [2,2,2,2,2]:
        print "passed"
    else:
        print "failed"

测试：

>>> runTests()
passed
passed
passed

在我的电脑上，这个操作耗时56秒：

primes = sieve(14000000) # 14 million!

例子：

>>> primes[:10]
[[], [], [2], [3], [2, 2], [5], [2, 3], [7], [2, 2, 2], [3, 3]]

>>> primes[10000]
[2, 2, 2, 2, 5, 5, 5, 5]

>>> primes[65536]
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

>>> primes[6561]
[3, 3, 3, 3, 3, 3, 3, 3]

>>> primes[233223]
[3, 17, 17, 269]

内存消耗：大约5000万个整数，分布在1400万个列表中：

>>> sum(map(len, primes))
53303934

- Matt Fenwick

---

干得好。我需要更深入地研究筛法，并将其用作示例。（我仍然对内存需求持谨慎态度...但这可能是由于我很久以前[可能是错误的]将筛选阶段实现为独立对象，每个对象都有自己的内存需求。） - Dan H

Answer 3

递归（伪代码）：

def get_factorizations_of_all_numbers( start = starting_point
                                     , end = end_point
                                     , minp = mimimum_prime
                                     ):
    if start > end:
        return Empty_List
    if minp ^ 2 > end:
        return list_of_all_primes( start, end )
    else
        a = minp * get_factorizations_of_all_numbers( rounddown(start/minp)
                                                    , roundup(end/minp)
                                                    )
        b = get_factorizations_of_all_numbers( start
                                             , end
                                             , next_prime( minp )
                                             )
        return append( a , b )

get_factorizations_of_all_numbers( 1, n, 2 )

- ypercubeᵀᴹ

---

谢谢。在我看来，这个伪代码基本上与@catchmeifyoutry的实现相同。(至于使用minp ^ 2 > end进行测试：我有一种预感，这只是最微小的优化之一，因为下一个递归“in”到自身通过end=end/minp将有效地捕获相同的条件。) - Dan H