有效地生成小于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)。当完成与该素数的所有组合时，将其删除，然后用素数生成器上可用的下一个最低素数重复。
我试图用“递归生成器”来实现这一点，这让我非常困惑什么时候应该从递归中跳出来，使用“产生"，或者”提高StopIteration"，或者“返回”，或者干脆从递归函数中跳出来。
谢谢你的智慧！
补充说明：
我现在有一种方法可以做到这一点:我已经写了一个函数来计算数字，所以我可以把它们分解成素数，然后得到结果。没问题。我依靠“N的最低素数因子是什么”的高速缓存来保持这个速度。高达一千万美元。
然而，一旦我离开缓存，我们将，它将转移到“天真的”保理。(恶心)
这一职位的要点是：
- 我假设“从它们的因素生成大型复合材料”比“分解大型复合材料”要快.尤其是我不关心订单，
- ，您怎么能让Python生成器“递归地”调用自己，并产生单个生成的东西流呢？
回答 3
Stack Overflow用户
发布于 2012-04-11 16:26:17
假设primesiter(n)在n之前的所有素数上创建了一个迭代器( primesiter中不应该包含1)，或者下面的代码很好地输入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)输出
>> 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而不是元组。如果需要的话，这两个问题都可以很容易地解决，但我将把这作为一个练习。
Stack Overflow用户
发布于 2012-04-11 16:45:04
下面是一个基于筛子的实现(请原谅un代码: )：
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]内存消耗:1400万个列表中的大约5000万个整数：
>>> sum(map(len, primes))
53303934Stack Overflow用户
发布于 2012-04-11 16:42:00
递归(伪代码)：
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 )https://stackoverflow.com/questions/10109510
复制相似问题
腾讯云开发者
