这是我能想到的最好的算法。
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
很抱歉打扰，但erat2()在算法中有一个严重的缺陷。
在搜索下一个合成时，我们只需要测试奇数。
Q p都是奇数;那么q+p是偶数，不需要检验，但q+2*p总是奇数。这消除了while循环条件中的“if even”测试，并节省了大约30%的运行时。
当我们在它:而不是优雅的'D.pop(q,None)'获取和删除方法，使用'if q in D: p=D[q]，del D[q]'，这是两倍的速度!至少在我的机器上(P3-1Ghz)。
所以我建议这个聪明算法的实现:
def erat3( ):
from itertools import islice, count
# q is the running integer that's checked for primeness.
# yield 2 and no other even number thereafter
yield 2
D = {}
# no need to mark D[4] as we will test odd numbers only
for q in islice(count(3),0,None,2):
if q in D: # is composite
p = D[q]
del D[q]
# q is composite. p=D[q] is the first prime that
# divides it. Since we've reached q, we no longer
# need it in the map, but we'll mark the next
# multiple of its witnesses to prepare for larger
# numbers.
x = q + p+p # next odd(!) multiple
while x in D: # skip composites
x += p+p
D[x] = p
else: # is prime
# q is a new prime.
# Yield it and mark its first multiple that isn't
# already marked in previous iterations.
D[q*q] = q
yield q
下面是我在Python中通常用来生成质数的代码:
$ python -mtimeit -s'import sieve' 'sieve.sieve(1000000)'
10 loops, best of 3: 445 msec per loop
$ cat sieve.py
from math import sqrt
def sieve(size):
prime=[True]*size
rng=xrange
limit=int(sqrt(size))
for i in rng(3,limit+1,+2):
if prime[i]:
prime[i*i::+i]=[False]*len(prime[i*i::+i])
return [2]+[i for i in rng(3,size,+2) if prime[i]]
if __name__=='__main__':
print sieve(100)
它不能与这里发布的更快的解决方案竞争，但至少它是纯python。
谢谢你提出这个问题。我今天真的学到了很多东西。
你有一个更快的代码和最简单的代码生成质数。
但对于更大的数字，当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我认为更快。
然而，我无法理解时间的复杂性。
