我想构建一个高效的Python迭代器/生成器,该生成器可产生:
假设我们已经有了一个小于N的质数列表或可以执行相同操作的质数生成器。
请注意,我:
例如,对composites_with_factors(16)的调用可能会产生:
- 小于N的所有合数
- 以及它们的素因子分解
假设我们已经有了一个小于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生成器“递归”调用自身并产生单个生成的流?