这是我能想到的最好的算法。
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
这些都是经过编写和测试的。所以没有必要重新发明轮子。
python -m timeit -r10 -s"from sympy import sieve" "primes = list(sieve.primerange(1, 10**6))"
打破了12.2秒的记录!
10 loops, best of 10: 12.2 msec per loop
如果这还不够快，你可以试试PyPy:
pypy -m timeit -r10 -s"from sympy import sieve" "primes = list(sieve.primerange(1, 10**6))"
结果是:
10 loops, best of 10: 2.03 msec per loop
得到247张赞成票的答案列出了15.9毫秒的最佳解决方案。
比较这个! !
你有一个更快的代码和最简单的代码生成质数。
但对于更大的数字，当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我认为更快。
然而，我无法理解时间的复杂性。
在Pure Python中最快的质数筛分:
from itertools import compress
def half_sieve(n):
"""
Returns a list of prime numbers less than `n`.
"""
if n <= 2:
return []
sieve = bytearray([True]) * (n // 2)
for i in range(3, int(n ** 0.5) + 1, 2):
if sieve[i // 2]:
sieve[i * i // 2::i] = bytearray((n - i * i - 1) // (2 * i) + 1)
primes = list(compress(range(1, n, 2), sieve))
primes[0] = 2
return primes
我优化了埃拉托色尼筛子的速度和内存。
基准
from time import clock
import platform
def benchmark(iterations, limit):
start = clock()
for x in range(iterations):
half_sieve(limit)
end = clock() - start
print(f'{end/iterations:.4f} seconds for primes < {limit}')
if __name__ == '__main__':
print(platform.python_version())
print(platform.platform())
print(platform.processor())
it = 10
for pw in range(4, 9):
benchmark(it, 10**pw)
输出
>>> 3.6.7
>>> Windows-10-10.0.17763-SP0
>>> Intel64 Family 6 Model 78 Stepping 3, GenuineIntel
>>> 0.0003 seconds for primes < 10000
>>> 0.0021 seconds for primes < 100000
>>> 0.0204 seconds for primes < 1000000
>>> 0.2389 seconds for primes < 10000000
>>> 2.6702 seconds for primes < 100000000
