<p>这不需要使用两个函数来完成,但这里是生成“n”以下素数的一般方法(我相信是最快的方法),使用<a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow">Sieve of Eratosthenes</a>:</p>
<pre><code>def prevPrimes(n):
"""Generates a list of primes up to 'n'"""
from numbers import Integral as types #'Integral' is a class of integers/long-numbers
if not isinstance(n, types): raise TypeError("n must be int, not " + str(type(n)))
if n < 2: raise ValueError("n must greater than 2")
primes_dict = {i : True for i in range(2, n + 1)} # initializes the dictionary
for i in primes_dict:
if primes_dict[i]: #avoids going through multiples of numbers already declared False
num = 2
while (num * i <= n): #sets all multiples of i (up to n) as False
primes_dict[num*i] = False
num += 1
return [num for num in primes_dict if primes_dict[num]]
</code></pre>
<p>正如jackj所指出的,避免使用所有偶数可以使代码更快。你知道吗</p>
<pre><code>def primes(n):
"""Generates a list of primes up to 'n'"""
primes_dict = {i : True for i in range(3, n + 1, 2)} # this does not
for i in primes_dict:
if primes_dict[i]:
num = 3
while (num * i <= n):
primes_dict[num*i] = False
num += 2
primes_dict[2] = True
return [num for num in primes_dict if primes_dict[num]]
</code></pre>
<p>然后运行测试:</p>
<pre><code>from timeit import timeit
def test1():
return primes(1000)
print 'Without Evens: ', timeit(test1, number=1000)
print 'With Evens: ', timeit(stmt='prevPrimes(1000)', setup='from nums import prevPrimes', number=1000)
</code></pre>
<p>输出:</p>
<pre><code>>>>
Without Evens: 1.22693896972
With Evens: 3.01304618635
</code></pre>