这是我能想到的最好的算法。
def get_primes(n):
numbers = set(range(n, 1, -1))
primes = []
while numbers:
p = numbers.pop()
primes.append(p)
numbers.difference_update(set(range(p*2, n+1, p)))
return primes
>>> timeit.Timer(stmt='get_primes.get_primes(1000000)', setup='import get_primes').timeit(1)
1.1499958793645562
还能做得更快吗?
这段代码有一个缺陷:由于numbers是一个无序集，不能保证numbers.pop()将从集合中移除最低的数字。尽管如此，它还是适用于(至少对我来说)一些输入数字:
>>> sum(get_primes(2000000))
142913828922L
#That's the correct sum of all numbers below 2 million
>>> 529 in get_primes(1000)
False
>>> 529 in get_primes(530)
True
你有一个更快的代码和最简单的代码生成质数。
但对于更大的数字，当n=10000, 10000000时，它不起作用，可能是。pop()方法失败了
考虑:N是质数吗?
case 1:
You got some factors of N,
for i in range(2, N):
If N is prime loop is performed for ~(N-2) times. else less number of times
case 2:
for i in range(2, int(math.sqrt(N)):
Loop is performed for almost ~(sqrt(N)-2) times if N is prime else will break somewhere
case 3:
Better We Divide N With Only number of primes<=sqrt(N)
Where loop is performed for only π(sqrt(N)) times
π(sqrt(N)) << sqrt(N) as N increases
from math import sqrt
from time import *
prime_list = [2]
n = int(input())
s = time()
for n0 in range(2,n+1):
for i0 in prime_list:
if n0%i0==0:
break
elif i0>=int(sqrt(n0)):
prime_list.append(n0)
break
e = time()
print(e-s)
#print(prime_list); print(f'pi({n})={len(prime_list)}')
print(f'{n}: {len(prime_list)}, time: {e-s}')
Output
100: 25, time: 0.00010275840759277344
1000: 168, time: 0.0008606910705566406
10000: 1229, time: 0.015588521957397461
100000: 9592, time: 0.023436546325683594
1000000: 78498, time: 4.1965954303741455
10000000: 664579, time: 109.24591708183289
100000000: 5761455, time: 2289.130858898163
小于1000似乎很慢，但小于10^6我认为更快。
然而，我无法理解时间的复杂性。
这里有一个来自Python Cookbook的非常简洁的示例——该URL的最快版本是:
import itertools
def erat2( ):
D = { }
yield 2
for q in itertools.islice(itertools.count(3), 0, None, 2):
p = D.pop(q, None)
if p is None:
D[q*q] = q
yield q
else:
x = p + q
while x in D or not (x&1):
x += p
D[x] = p
这就给出了
def get_primes_erat(n):
return list(itertools.takewhile(lambda p: p<n, erat2()))
在shell提示符(正如我喜欢做的那样)中测量这段代码在pri.py中，我观察到:
$ python2.5 -mtimeit -s'import pri' 'pri.get_primes(1000000)'
10 loops, best of 3: 1.69 sec per loop
$ python2.5 -mtimeit -s'import pri' 'pri.get_primes_erat(1000000)'
10 loops, best of 3: 673 msec per loop
所以看起来食谱解决方案的速度是原来的两倍多。
使用Sundaram的Sieve，我想我打破了pure-Python的记录:
def sundaram3(max_n):
numbers = range(3, max_n+1, 2)
half = (max_n)//2
initial = 4
for step in xrange(3, max_n+1, 2):
for i in xrange(initial, half, step):
numbers[i-1] = 0
initial += 2*(step+1)
if initial > half:
return [2] + filter(None, numbers)
Comparasion:
C:\USERS>python -m timeit -n10 -s "import get_primes" "get_primes.get_primes_erat(1000000)"
10 loops, best of 3: 710 msec per loop
C:\USERS>python -m timeit -n10 -s "import get_primes" "get_primes.daniel_sieve_2(1000000)"
10 loops, best of 3: 435 msec per loop
C:\USERS>python -m timeit -n10 -s "import get_primes" "get_primes.sundaram3(1000000)"
10 loops, best of 3: 327 msec per loop
