<p>现有代码缩进错误。我假设这个任务是一个家庭作业任务,所以我不会发布一个完整的解决方案,但我会给你一些有用的片段。在</p>
<p>首先,这里有一个稍微更有效的素性测试程序。它不是测试所有小于<code>a</code>的数字是否都是<code>a</code>的因子,而是测试<code>a</code>的平方根。在</p>
<pre><code>def is_prime(a):
for i in xrange(2, int(1 + a ** 0.5)):
if a % i == 0:
return False
return True
</code></pre>
<p>请注意,此函数为<code>a = 1</code>返回<code>True</code>。没关系,因为您不需要测试1:您可以将它预加载到<code>lookup</code>dict中:</p>
^{pr2}$
<p>您的<code>countTerms</code>函数需要稍作修改,以便在当前<code>n</code>为素数时,它只在<code>lookup</code>计数中添加一个。在Python中,<code>False</code>的数值为0,<code>True</code>的数值为1。这里很方便:</p>
<pre><code>def count_prime_terms(n):
''' Count the number of primes terms in a Collatz sequence '''
if n not in lookup:
if n % 2:
next_n = n * 3 + 1
else:
next_n = n // 2
lookup[n] = count_prime_terms(next_n) + is_prime(n)
return lookup[n]
</code></pre>
<p>我已经把函数名改成了Pythonic。在</p>
<p>FWIW,第一个包含65个或更多素数的Collatz序列实际上包含67个素数。它的种子数超过180万个,当检查到该种子的所有序列时,需要进行素性测试的最高数目是151629574372。完成时,<code>lookup</code>dict包含3920492个条目。在</p>
<hr/>
<p>为了回应jamesmills关于递归的评论,我写了一个非递归的版本,为了容易地看到迭代版本和递归版本都产生相同的结果,我发布了一个完整的工作程序。我在上面说过我不打算这么做,但我认为现在这样做应该是可以的,因为spørreren已经使用我在原始答案中提供的信息编写了他们的程序。在</p>
<p>我完全同意避免递归是好的,除非它适合于问题域(例如,树遍历)。Python不鼓励递归-它不能优化尾部调用递归,它施加了递归深度限制(尽管如果需要,可以修改该限制)。在</p>
<p>这个Collatz序列素数计算算法自然地递归地表示,但是迭代地做并不难——我们只需要一个列表,在确定序列所有成员的素数时暂时保存序列。这个版本可能需要更多的内存空间。在</p>
<p>当在操作中解决问题时,递归版本达到了343的递归深度。这在默认限制范围内,但仍然不好,如果你想搜索包含更多素数的序列,你会达到这个极限。在</p>
<p>迭代和递归版本的运行速度大致相同(至少在我的机器上是这样)。要解决OP中提到的问题,他们都需要不到2分钟的时间。这比我原来的解决方案快得多,主要是由于素性测试中的优化。在</p>
<p>基本的Collatz序列生成步骤已经需要确定一个数是奇数还是偶数。显然,如果我们已经知道一个数是偶数,那么就没有必要测试它是否是质数。:)我们还可以消除<code>is_prime</code>函数中的偶数因子测试。我们只需将2的结果加载到<code>lookup</code>缓存中,就可以处理2是素数这一事实。在</p>
<p>另一方面,当搜索包含给定数量素数的第一个序列时,我们不需要测试任何从偶数开始的序列。偶数(除了2)不会增加序列的素数,而且由于这样一个序列中的第一个奇数将比我们当前的数字低,所以假设我们从3开始搜索,它的结果将已经在<code>lookup</code>缓存中。如果我们不从3开始搜索,我们只需要确保我们的起始种子足够低,这样我们就不会意外地错过包含所需数量素数的第一个序列。采用这种策略不仅减少了所需的时间,还减少了项目的数量在查找缓存中。在</p>
<pre><code>#!/usr/bin/env python
''' Find the 1st Collatz sequence containing a given number of prime terms
From http://stackoverflow.com/q/29920691/4014959
Written by PM 2Ring 2015.04.29
[Seed == 1805311, prime count == 67]
'''
import sys
def is_prime(a):
''' Test if odd `a` >= 3 is prime '''
for i in xrange(3, int(1 + a ** 0.5), 2):
if not a % i:
return 0
return 1
#Track the highest number generated so far; use a list
# so we don't have to declare it as global...
hi = [2]
#Cache for sequence prime counts. The key is the sequence seed,
# the value is the number of primes in that sequence.
lookup = {1:0, 2:1}
def count_prime_terms_iterative(n):
''' Count the number of primes terms in a Collatz sequence
Iterative version '''
seq = []
while n not in lookup:
if n > hi[0]:
hi[0] = n
if n % 2:
seq.append((n, is_prime(n)))
n = n * 3 + 1
else:
seq.append((n, 0))
n = n // 2
count = lookup[n]
for n, isprime in reversed(seq):
count += isprime
lookup[n] = count
return count
def count_prime_terms_recursive(n):
''' Count the number of primes terms in a Collatz sequence
Recursive version '''
if n not in lookup:
if n > hi[0]:
hi[0] = n
if n % 2:
next_n = n * 3 + 1
isprime = is_prime(n)
else:
next_n = n // 2
isprime = 0
lookup[n] = count_prime_terms(next_n) + isprime
return lookup[n]
def find_seed(numprimes, start):
''' Find the seed of the 1st Collatz sequence containing
`numprimes` primes, starting from odd seed `start` '''
i = start
mcount = 0
print 'seed, prime count, highest term, dict size'
while mcount < numprimes:
count = count_prime_terms(i)
if count > mcount:
mcount = count
print i, count, hi[0], len(lookup)
i += 2
#count_prime_terms = count_prime_terms_recursive
count_prime_terms = count_prime_terms_iterative
def main():
if len(sys.argv) > 1:
numprimes = int(sys.argv[1])
else:
print 'Usage: %s numprimes [start]' % sys.argv[0]
exit()
start = int(sys.argv[2]) if len(sys.argv) > 2 else 3
#Round `start` up to the next odd number
if start % 2 == 0:
start += 1
find_seed(numprimes, start)
if __name__ == '__main__':
main()
</code></pre>
<p>当与</p>
<p><code>$ ./CollatzPrimes.py 65</code></p>
<p>输出是</p>
<pre><code>seed, prime count, highest term, dict size
3 3 16 8
7 6 52 18
19 7 160 35
27 25 9232 136
97 26 9232 230
171 28 9232 354
231 29 9232 459
487 30 39364 933
763 32 250504 1626
1071 36 250504 2197
4011 37 1276936 8009
6171 43 8153620 12297
10971 44 27114424 21969
17647 48 27114424 35232
47059 50 121012864 94058
99151 51 1570824736 198927
117511 52 2482111348 235686
202471 53 17202377752 405273
260847 55 17202377752 522704
481959 59 24648077896 966011
963919 61 56991483520 1929199
1564063 62 151629574372 3136009
1805311 67 151629574372 3619607
</code></pre>