有效地生成小于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).当完成与THAT素数的所有组合时,将其丢弃,并使用素数生成器上可用的下一个最低素数重复.

我试图用"递归生成器"来做这件事让我很惊讶什么时候用"yield","提升StopIteration"或"return"来弹出递归,或者简单地脱离递归函数.

谢谢你的智慧!

附加说明:

我现在有一种方法可以做到这一点:我已经编写了一个函数来计算数字,所以我可以将它们分解为素数,并产生结果.没问题.我依靠"N号最低素数因子"的缓存来保持这种速度极快...... N高达1000万.

但是,一旦我退出缓存,我们就会变成"天真"的因素.(呸).

这篇文章的重点是:

• 我假设"从他们的因素中产生大型复合材料"将比"考虑大型复合材料"更快......特别是因为我不关心订单,
• 你怎么能"递归地"调用自己的Python生成器,并产生一个生成的东西流？

Answer 1

假设primesiter(n)在所有素数上创建一个迭代器n(1不应包括在内primesiter,或者在代码之后输入inf.loop)

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),我使用list而不是元组.如果需要,两者都可以轻松解决,但我会将其作为练习.