这不使用两个函数来做到这一点,但这是使用Eratosthenes 的 Sieve生成最高为 'n' 的素数的一般(我相信是最快的)方法:
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]]
正如 Jack J 所指出的,避免使用所有偶数会使这段代码更快。
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]]
然后运行测试:
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)
输出:
>>>
Without Evens: 1.22693896972
With Evens: 3.01304618635