N 이하의 모든 소수를 나열하는 가장 빠른 방법
이게 내가 생각해낸 최고의 알고리즘이야
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
더 빨리 만들 수 있을까요?
에는 결함이 이드코 this this this this this this this 。★★numbers가 매겨져 있지 않은 이므로, 「무조건」, 「무조건」, 「무조건」은 보증되지 않습니다.numbers.pop()이치노의 입력 가 있습니다: ada, 개적입적적 never적 （ 적적적적적적 ） 。
>>> 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
★★★★ timeit결과는 하드웨어 또는 Python 버전에 따라 다를 수 있습니다.
다음으로 몇 가지 구현을 비교하는 스크립트를 나타냅니다.
- ambi_module_module,
- rwh_primes,
- rwh_primes1,
- rwh_primes2,
- siefOfAtkin,
- 체 Of Eratostenes,
- sundaram3,
- 체_휠_30,
- ambi_py (numpy)
- 소수점 3에서 소수점 이하(numpy)
- 소수점 2 ~ (소수 numpy)
sieve_wheel_30을 알려주신 stephan님 감사합니다.Robert William Hanks는 소수점 2부터 소수점 3부터 소수점 3까지, rwh_primes, rwh_primes1, 및 rwh_primes2를 인정받습니다.
psyco를 사용하여 n=12000에 대해 테스트한 일반 Python 방법 중 rwh_primes1이 가장 빠르게 테스트되었습니다.
+---------------------+-------+
| Method | ms |
+---------------------+-------+
| rwh_primes1 | 43.0 |
| sieveOfAtkin | 46.4 |
| rwh_primes | 57.4 |
| sieve_wheel_30 | 63.0 |
| rwh_primes2 | 67.8 |
| sieveOfEratosthenes | 147.0 |
| ambi_sieve_plain | 152.0 |
| sundaram3 | 194.0 |
+---------------------+-------+
psyco 없이 n=42000에 대해 테스트된 일반 Python 방법 중 rwh_primes2가 가장 빨랐다.
+---------------------+-------+
| Method | ms |
+---------------------+-------+
| rwh_primes2 | 68.1 |
| rwh_primes1 | 93.7 |
| rwh_primes | 94.6 |
| sieve_wheel_30 | 97.4 |
| sieveOfEratosthenes | 178.0 |
| ambi_sieve_plain | 286.0 |
| sieveOfAtkin | 314.0 |
| sundaram3 | 416.0 |
+---------------------+-------+
모든 테스트 방법 중 n=numpy를 허용하여 n=numpy에서 primes2 to가 가장 빠르게 테스트되었다.
+---------------------+-------+
| Method | ms |
+---------------------+-------+
| primesfrom2to | 15.9 |
| primesfrom3to | 18.4 |
| ambi_sieve | 29.3 |
+---------------------+-------+
타이밍은 다음 명령을 사용하여 측정되었습니다.
python -mtimeit -s"import primes" "primes.{method}(1000000)"
{method}각 메서드 이름으로 대체됩니다.
primes.py:
#!/usr/bin/env python
import psyco; psyco.full()
from math import sqrt, ceil
import numpy as np
def rwh_primes(n):
# https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Returns a list of primes < n """
sieve = [True] * n
for i in xrange(3,int(n**0.5)+1,2):
if sieve[i]:
sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
return [2] + [i for i in xrange(3,n,2) if sieve[i]]
def rwh_primes1(n):
# https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Returns a list of primes < n """
sieve = [True] * (n/2)
for i in xrange(3,int(n**0.5)+1,2):
if sieve[i/2]:
sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]
def rwh_primes2(n):
# https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Input n>=6, Returns a list of primes, 2 <= p < n """
correction = (n%6>1)
n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
sieve = [True] * (n/3)
sieve[0] = False
for i in xrange(int(n**0.5)/3+1):
if sieve[i]:
k=3*i+1|1
sieve[ ((k*k)/3) ::2*k]=[False]*((n/6-(k*k)/6-1)/k+1)
sieve[(k*k+4*k-2*k*(i&1))/3::2*k]=[False]*((n/6-(k*k+4*k-2*k*(i&1))/6-1)/k+1)
return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]]
def sieve_wheel_30(N):
# http://zerovolt.com/?p=88
''' Returns a list of primes <= N using wheel criterion 2*3*5 = 30
Copyright 2009 by zerovolt.com
This code is free for non-commercial purposes, in which case you can just leave this comment as a credit for my work.
If you need this code for commercial purposes, please contact me by sending an email to: info [at] zerovolt [dot] com.'''
__smallp = ( 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139,
149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227,
229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311,
313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401,
409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491,
499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,
601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683,
691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797,
809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887,
907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997)
wheel = (2, 3, 5)
const = 30
if N < 2:
return []
if N <= const:
pos = 0
while __smallp[pos] <= N:
pos += 1
return list(__smallp[:pos])
# make the offsets list
offsets = (7, 11, 13, 17, 19, 23, 29, 1)
# prepare the list
p = [2, 3, 5]
dim = 2 + N // const
tk1 = [True] * dim
tk7 = [True] * dim
tk11 = [True] * dim
tk13 = [True] * dim
tk17 = [True] * dim
tk19 = [True] * dim
tk23 = [True] * dim
tk29 = [True] * dim
tk1[0] = False
# help dictionary d
# d[a , b] = c ==> if I want to find the smallest useful multiple of (30*pos)+a
# on tkc, then I need the index given by the product of [(30*pos)+a][(30*pos)+b]
# in general. If b < a, I need [(30*pos)+a][(30*(pos+1))+b]
d = {}
for x in offsets:
for y in offsets:
res = (x*y) % const
if res in offsets:
d[(x, res)] = y
# another help dictionary: gives tkx calling tmptk[x]
tmptk = {1:tk1, 7:tk7, 11:tk11, 13:tk13, 17:tk17, 19:tk19, 23:tk23, 29:tk29}
pos, prime, lastadded, stop = 0, 0, 0, int(ceil(sqrt(N)))
# inner functions definition
def del_mult(tk, start, step):
for k in xrange(start, len(tk), step):
tk[k] = False
# end of inner functions definition
cpos = const * pos
while prime < stop:
# 30k + 7
if tk7[pos]:
prime = cpos + 7
p.append(prime)
lastadded = 7
for off in offsets:
tmp = d[(7, off)]
start = (pos + prime) if off == 7 else (prime * (const * (pos + 1 if tmp < 7 else 0) + tmp) )//const
del_mult(tmptk[off], start, prime)
# 30k + 11
if tk11[pos]:
prime = cpos + 11
p.append(prime)
lastadded = 11
for off in offsets:
tmp = d[(11, off)]
start = (pos + prime) if off == 11 else (prime * (const * (pos + 1 if tmp < 11 else 0) + tmp) )//const
del_mult(tmptk[off], start, prime)
# 30k + 13
if tk13[pos]:
prime = cpos + 13
p.append(prime)
lastadded = 13
for off in offsets:
tmp = d[(13, off)]
start = (pos + prime) if off == 13 else (prime * (const * (pos + 1 if tmp < 13 else 0) + tmp) )//const
del_mult(tmptk[off], start, prime)
# 30k + 17
if tk17[pos]:
prime = cpos + 17
p.append(prime)
lastadded = 17
for off in offsets:
tmp = d[(17, off)]
start = (pos + prime) if off == 17 else (prime * (const * (pos + 1 if tmp < 17 else 0) + tmp) )//const
del_mult(tmptk[off], start, prime)
# 30k + 19
if tk19[pos]:
prime = cpos + 19
p.append(prime)
lastadded = 19
for off in offsets:
tmp = d[(19, off)]
start = (pos + prime) if off == 19 else (prime * (const * (pos + 1 if tmp < 19 else 0) + tmp) )//const
del_mult(tmptk[off], start, prime)
# 30k + 23
if tk23[pos]:
prime = cpos + 23
p.append(prime)
lastadded = 23
for off in offsets:
tmp = d[(23, off)]
start = (pos + prime) if off == 23 else (prime * (const * (pos + 1 if tmp < 23 else 0) + tmp) )//const
del_mult(tmptk[off], start, prime)
# 30k + 29
if tk29[pos]:
prime = cpos + 29
p.append(prime)
lastadded = 29
for off in offsets:
tmp = d[(29, off)]
start = (pos + prime) if off == 29 else (prime * (const * (pos + 1 if tmp < 29 else 0) + tmp) )//const
del_mult(tmptk[off], start, prime)
# now we go back to top tk1, so we need to increase pos by 1
pos += 1
cpos = const * pos
# 30k + 1
if tk1[pos]:
prime = cpos + 1
p.append(prime)
lastadded = 1
for off in offsets:
tmp = d[(1, off)]
start = (pos + prime) if off == 1 else (prime * (const * pos + tmp) )//const
del_mult(tmptk[off], start, prime)
# time to add remaining primes
# if lastadded == 1, remove last element and start adding them from tk1
# this way we don't need an "if" within the last while
if lastadded == 1:
p.pop()
# now complete for every other possible prime
while pos < len(tk1):
cpos = const * pos
if tk1[pos]: p.append(cpos + 1)
if tk7[pos]: p.append(cpos + 7)
if tk11[pos]: p.append(cpos + 11)
if tk13[pos]: p.append(cpos + 13)
if tk17[pos]: p.append(cpos + 17)
if tk19[pos]: p.append(cpos + 19)
if tk23[pos]: p.append(cpos + 23)
if tk29[pos]: p.append(cpos + 29)
pos += 1
# remove exceeding if present
pos = len(p) - 1
while p[pos] > N:
pos -= 1
if pos < len(p) - 1:
del p[pos+1:]
# return p list
return p
def sieveOfEratosthenes(n):
"""sieveOfEratosthenes(n): return the list of the primes < n."""
# Code from: <dickinsm@gmail.com>, Nov 30 2006
# http://groups.google.com/group/comp.lang.python/msg/f1f10ced88c68c2d
if n <= 2:
return []
sieve = range(3, n, 2)
top = len(sieve)
for si in sieve:
if si:
bottom = (si*si - 3) // 2
if bottom >= top:
break
sieve[bottom::si] = [0] * -((bottom - top) // si)
return [2] + [el for el in sieve if el]
def sieveOfAtkin(end):
"""sieveOfAtkin(end): return a list of all the prime numbers <end
using the Sieve of Atkin."""
# Code by Steve Krenzel, <Sgk284@gmail.com>, improved
# Code: https://web.archive.org/web/20080324064651/http://krenzel.info/?p=83
# Info: http://en.wikipedia.org/wiki/Sieve_of_Atkin
assert end > 0
lng = ((end-1) // 2)
sieve = [False] * (lng + 1)
x_max, x2, xd = int(sqrt((end-1)/4.0)), 0, 4
for xd in xrange(4, 8*x_max + 2, 8):
x2 += xd
y_max = int(sqrt(end-x2))
n, n_diff = x2 + y_max*y_max, (y_max << 1) - 1
if not (n & 1):
n -= n_diff
n_diff -= 2
for d in xrange((n_diff - 1) << 1, -1, -8):
m = n % 12
if m == 1 or m == 5:
m = n >> 1
sieve[m] = not sieve[m]
n -= d
x_max, x2, xd = int(sqrt((end-1) / 3.0)), 0, 3
for xd in xrange(3, 6 * x_max + 2, 6):
x2 += xd
y_max = int(sqrt(end-x2))
n, n_diff = x2 + y_max*y_max, (y_max << 1) - 1
if not(n & 1):
n -= n_diff
n_diff -= 2
for d in xrange((n_diff - 1) << 1, -1, -8):
if n % 12 == 7:
m = n >> 1
sieve[m] = not sieve[m]
n -= d
x_max, y_min, x2, xd = int((2 + sqrt(4-8*(1-end)))/4), -1, 0, 3
for x in xrange(1, x_max + 1):
x2 += xd
xd += 6
if x2 >= end: y_min = (((int(ceil(sqrt(x2 - end))) - 1) << 1) - 2) << 1
n, n_diff = ((x*x + x) << 1) - 1, (((x-1) << 1) - 2) << 1
for d in xrange(n_diff, y_min, -8):
if n % 12 == 11:
m = n >> 1
sieve[m] = not sieve[m]
n += d
primes = [2, 3]
if end <= 3:
return primes[:max(0,end-2)]
for n in xrange(5 >> 1, (int(sqrt(end))+1) >> 1):
if sieve[n]:
primes.append((n << 1) + 1)
aux = (n << 1) + 1
aux *= aux
for k in xrange(aux, end, 2 * aux):
sieve[k >> 1] = False
s = int(sqrt(end)) + 1
if s % 2 == 0:
s += 1
primes.extend([i for i in xrange(s, end, 2) if sieve[i >> 1]])
return primes
def ambi_sieve_plain(n):
s = range(3, n, 2)
for m in xrange(3, int(n**0.5)+1, 2):
if s[(m-3)/2]:
for t in xrange((m*m-3)/2,(n>>1)-1,m):
s[t]=0
return [2]+[t for t in s if t>0]
def sundaram3(max_n):
# https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/2073279#2073279
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)
################################################################################
# Using Numpy:
def ambi_sieve(n):
# http://tommih.blogspot.com/2009/04/fast-prime-number-generator.html
s = np.arange(3, n, 2)
for m in xrange(3, int(n ** 0.5)+1, 2):
if s[(m-3)/2]:
s[(m*m-3)/2::m]=0
return np.r_[2, s[s>0]]
def primesfrom3to(n):
# https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Returns a array of primes, p < n """
assert n>=2
sieve = np.ones(n/2, dtype=np.bool)
for i in xrange(3,int(n**0.5)+1,2):
if sieve[i/2]:
sieve[i*i/2::i] = False
return np.r_[2, 2*np.nonzero(sieve)[0][1::]+1]
def primesfrom2to(n):
# https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Input n>=6, Returns a array of primes, 2 <= p < n """
sieve = np.ones(n/3 + (n%6==2), dtype=np.bool)
sieve[0] = False
for i in xrange(int(n**0.5)/3+1):
if sieve[i]:
k=3*i+1|1
sieve[ ((k*k)/3) ::2*k] = False
sieve[(k*k+4*k-2*k*(i&1))/3::2*k] = False
return np.r_[2,3,((3*np.nonzero(sieve)[0]+1)|1)]
if __name__=='__main__':
import itertools
import sys
def test(f1,f2,num):
print('Testing {f1} and {f2} return same results'.format(
f1=f1.func_name,
f2=f2.func_name))
if not all([a==b for a,b in itertools.izip_longest(f1(num),f2(num))]):
sys.exit("Error: %s(%s) != %s(%s)"%(f1.func_name,num,f2.func_name,num))
n=1000000
test(sieveOfAtkin,sieveOfEratosthenes,n)
test(sieveOfAtkin,ambi_sieve,n)
test(sieveOfAtkin,ambi_sieve_plain,n)
test(sieveOfAtkin,sundaram3,n)
test(sieveOfAtkin,sieve_wheel_30,n)
test(sieveOfAtkin,primesfrom3to,n)
test(sieveOfAtkin,primesfrom2to,n)
test(sieveOfAtkin,rwh_primes,n)
test(sieveOfAtkin,rwh_primes1,n)
test(sieveOfAtkin,rwh_primes2,n)
스크립트 테스트를 실행하여 모든 구현에서 동일한 결과를 얻을 수 있습니다.
더 빠르고 메모리 면에서도 더 많은 Python 코드:
def primes(n):
""" Returns a list of primes < n """
sieve = [True] * n
for i in range(3,int(n**0.5)+1,2):
if sieve[i]:
sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
return [2] + [i for i in range(3,n,2) if sieve[i]]
아니면 반쯤 체에 밭쳐서
def primes1(n):
""" Returns a list of primes < n """
sieve = [True] * (n//2)
for i in range(3,int(n**0.5)+1,2):
if sieve[i//2]:
sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
return [2] + [2*i+1 for i in range(1,n//2) if sieve[i]]
보다 빠르고 메모리 효율이 뛰어난 Numpy 코드:
import numpy
def primesfrom3to(n):
""" Returns a array of primes, 3 <= p < n """
sieve = numpy.ones(n//2, dtype=bool)
for i in range(3,int(n**0.5)+1,2):
if sieve[i//2]:
sieve[i*i//2::i] = False
return 2*numpy.nonzero(sieve)[0][1::]+1
체의 1/3부터 시작하는 더 빠른 변화:
import numpy
def primesfrom2to(n):
""" Input n>=6, Returns a array of primes, 2 <= p < n """
sieve = numpy.ones(n//3 + (n%6==2), dtype=bool)
for i in range(1,int(n**0.5)//3+1):
if sieve[i]:
k=3*i+1|1
sieve[ k*k//3 ::2*k] = False
sieve[k*(k-2*(i&1)+4)//3::2*k] = False
return numpy.r_[2,3,((3*numpy.nonzero(sieve)[0][1:]+1)|1)]
상기 코드의 (코드하기 어려운) 순수 피톤 버전은 다음과 같습니다.
def primes2(n):
""" Input n>=6, Returns a list of primes, 2 <= p < n """
n, correction = n-n%6+6, 2-(n%6>1)
sieve = [True] * (n//3)
for i in range(1,int(n**0.5)//3+1):
if sieve[i]:
k=3*i+1|1
sieve[ k*k//3 ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]
불행하게도 순수한 피톤은 더 간단하고 빠른 할당과 호출의 numpy 방식을 채택하지 않습니다.len()( 「」등)에 .[False]*len(sieve[((k*k)//3)::2*k])더 이상 을 하지 않기 으로 (더 수학을 하지 ) ) 마법을 .그래서 저는 정확한 입력을 위해 즉흥적으로 (더 많은 수학은 피하고) 극단적인 (& 고통스러운) 수학 마술을 해야 했습니다.
개인적으로 numpy가 Python 표준 라이브러리의 일부가 아니라는 것과 구문과 속도의 개선이 Python 개발자들에 의해 완전히 간과되고 있다는 것은 유감스러운 일이라고 생각합니다.
여기 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()))
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
쿡북 솔루션이 2배 이상 빠른 것 같습니다.
순다람의 체를 사용해서 순수 피스톤의 기록을 깬 것 같아요
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)
비교:
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
알고리즘은 빠르지만 심각한 결함이 있습니다.
>>> sorted(get_primes(530))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163,
167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251,
257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 527, 529]
>>> 17*31
527
>>> 23*23
529
은 「 「 」라고 .numbers.pop()이 경우 세트 내에서 가장 작은 숫자가 반환되지만 이는 전혀 보장되지 않습니다.가 뒤바뀌어 있습니다.pop()임의 요소를 제거하고 반환하므로 나머지 숫자에서 다음 소수를 선택하는 데 사용할 수 없습니다.
충분히 큰 N을 가진 정말로 빠른 솔루션을 얻으려면 미리 계산된 소수점 목록을 다운로드하여 태플에 저장하고 다음과 같은 작업을 수행합니다.
for pos,i in enumerate(primes):
if i > N:
print primes[:pos]
ifN > primes[-1] 그런 다음 더 많은 소수점을 계산하고 새 목록을 코드에 저장하기 때문에 다음 번에도 마찬가지로 빠릅니다.
항상 고정관념에서 벗어나세요.
휠을 재창조하고 싶지 않다면 심볼 수학 라이브러리를 설치할 수 있습니다(Python 3 호환).
pip install sympy
그리고 프라이머레인지 기능을 사용합니다.
from sympy import sieve
primes = list(sieve.primerange(1, 10**6))
만약 당신이 numpy가 아닌 itertools를 받아들인다면, 여기 python 3의 rwh_primes2가 내 기계에서 약 2배 빠르게 동작합니다.유일하게 큰 변화는 부울 리스트 대신 바이얼레이를 사용하고 최종 리스트를 작성하기 위해 리스트 이해 대신 압축을 사용하는 것입니다(가능한 경우 moaringsun과 같은 코멘트로 추가합니다).
import itertools
izip = itertools.zip_longest
chain = itertools.chain.from_iterable
compress = itertools.compress
def rwh_primes2_python3(n):
""" Input n>=6, Returns a list of primes, 2 <= p < n """
zero = bytearray([False])
size = n//3 + (n % 6 == 2)
sieve = bytearray([True]) * size
sieve[0] = False
for i in range(int(n**0.5)//3+1):
if sieve[i]:
k=3*i+1|1
start = (k*k+4*k-2*k*(i&1))//3
sieve[(k*k)//3::2*k]=zero*((size - (k*k)//3 - 1) // (2 * k) + 1)
sieve[ start ::2*k]=zero*((size - start - 1) // (2 * k) + 1)
ans = [2,3]
poss = chain(izip(*[range(i, n, 6) for i in (1,5)]))
ans.extend(compress(poss, sieve))
return ans
비교:
>>> timeit.timeit('primes.rwh_primes2(10**6)', setup='import primes', number=1)
0.0652179726976101
>>> timeit.timeit('primes.rwh_primes2_python3(10**6)', setup='import primes', number=1)
0.03267321276325674
그리고.
>>> timeit.timeit('primes.rwh_primes2(10**8)', setup='import primes', number=1)
6.394284538007014
>>> timeit.timeit('primes.rwh_primes2_python3(10**8)', setup='import primes', number=1)
3.833829450302801
자신만의 주요 검색 코드를 작성하는 것은 유익하지만, 빠르고 신뢰할 수 있는 라이브러리를 가까이에 두는 것도 유용합니다.나는 C++ 도서관 primesieve에 primesieve-python이라는 이름의 포장지를 썼다.
번 해봐.pip install primesieve
import primesieve
primes = primesieve.generate_primes(10**8)
속도 비교가 좀 궁금하네요.
여기 가장 빠른 기능 중 하나인 두 개의 업데이트된 버전(순정 Python 3.6)이 있습니다.
from itertools import compress
def rwh_primes1v1(n):
""" Returns a list of primes < n for n > 2 """
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)
return [2,*compress(range(3,n,2), sieve[1:])]
def rwh_primes1v2(n):
""" Returns a list of primes < n for n > 2 """
sieve = bytearray([True]) * (n//2+1)
for i in range(1,int(n**0.5)//2+1):
if sieve[i]:
sieve[2*i*(i+1)::2*i+1] = bytearray((n//2-2*i*(i+1))//(2*i+1)+1)
return [2,*compress(range(3,n,2), sieve[1:])]
Python 3의 코드 중 많은 부분을 업데이트하여 perfplot(내 프로젝트)에 던져서 어느 것이 실제로 빠른지 확인했습니다.알고 보니, 큰 사이즈의 경우n,primesfrom{2,3}to다음 중 하나:
플롯을 재현하는 코드:
import perfplot
from math import sqrt, ceil
import numpy as np
import sympy
def rwh_primes(n):
# https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Returns a list of primes < n """
sieve = [True] * n
for i in range(3, int(n ** 0.5) + 1, 2):
if sieve[i]:
sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
return [2] + [i for i in range(3, n, 2) if sieve[i]]
def rwh_primes1(n):
# https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Returns a list of primes < n """
sieve = [True] * (n // 2)
for i in range(3, int(n ** 0.5) + 1, 2):
if sieve[i // 2]:
sieve[i * i // 2::i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
return [2] + [2 * i + 1 for i in range(1, n // 2) if sieve[i]]
def rwh_primes2(n):
# https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
"""Input n>=6, Returns a list of primes, 2 <= p < n"""
assert n >= 6
correction = n % 6 > 1
n = {0: n, 1: n - 1, 2: n + 4, 3: n + 3, 4: n + 2, 5: n + 1}[n % 6]
sieve = [True] * (n // 3)
sieve[0] = False
for i in range(int(n ** 0.5) // 3 + 1):
if sieve[i]:
k = 3 * i + 1 | 1
sieve[((k * k) // 3)::2 * k] = [False] * (
(n // 6 - (k * k) // 6 - 1) // k + 1
)
sieve[(k * k + 4 * k - 2 * k * (i & 1)) // 3::2 * k] = [False] * (
(n // 6 - (k * k + 4 * k - 2 * k * (i & 1)) // 6 - 1) // k + 1
)
return [2, 3] + [3 * i + 1 | 1 for i in range(1, n // 3 - correction) if sieve[i]]
def sieve_wheel_30(N):
# http://zerovolt.com/?p=88
""" Returns a list of primes <= N using wheel criterion 2*3*5 = 30
Copyright 2009 by zerovolt.com
This code is free for non-commercial purposes, in which case you can just leave this comment as a credit for my work.
If you need this code for commercial purposes, please contact me by sending an email to: info [at] zerovolt [dot] com."""
__smallp = (
2,
3,
5,
7,
11,
13,
17,
19,
23,
29,
31,
37,
41,
43,
47,
53,
59,
61,
67,
71,
73,
79,
83,
89,
97,
101,
103,
107,
109,
113,
127,
131,
137,
139,
149,
151,
157,
163,
167,
173,
179,
181,
191,
193,
197,
199,
211,
223,
227,
229,
233,
239,
241,
251,
257,
263,
269,
271,
277,
281,
283,
293,
307,
311,
313,
317,
331,
337,
347,
349,
353,
359,
367,
373,
379,
383,
389,
397,
401,
409,
419,
421,
431,
433,
439,
443,
449,
457,
461,
463,
467,
479,
487,
491,
499,
503,
509,
521,
523,
541,
547,
557,
563,
569,
571,
577,
587,
593,
599,
601,
607,
613,
617,
619,
631,
641,
643,
647,
653,
659,
661,
673,
677,
683,
691,
701,
709,
719,
727,
733,
739,
743,
751,
757,
761,
769,
773,
787,
797,
809,
811,
821,
823,
827,
829,
839,
853,
857,
859,
863,
877,
881,
883,
887,
907,
911,
919,
929,
937,
941,
947,
953,
967,
971,
977,
983,
991,
997,
)
# wheel = (2, 3, 5)
const = 30
if N < 2:
return []
if N <= const:
pos = 0
while __smallp[pos] <= N:
pos += 1
return list(__smallp[:pos])
# make the offsets list
offsets = (7, 11, 13, 17, 19, 23, 29, 1)
# prepare the list
p = [2, 3, 5]
dim = 2 + N // const
tk1 = [True] * dim
tk7 = [True] * dim
tk11 = [True] * dim
tk13 = [True] * dim
tk17 = [True] * dim
tk19 = [True] * dim
tk23 = [True] * dim
tk29 = [True] * dim
tk1[0] = False
# help dictionary d
# d[a , b] = c ==> if I want to find the smallest useful multiple of (30*pos)+a
# on tkc, then I need the index given by the product of [(30*pos)+a][(30*pos)+b]
# in general. If b < a, I need [(30*pos)+a][(30*(pos+1))+b]
d = {}
for x in offsets:
for y in offsets:
res = (x * y) % const
if res in offsets:
d[(x, res)] = y
# another help dictionary: gives tkx calling tmptk[x]
tmptk = {1: tk1, 7: tk7, 11: tk11, 13: tk13, 17: tk17, 19: tk19, 23: tk23, 29: tk29}
pos, prime, lastadded, stop = 0, 0, 0, int(ceil(sqrt(N)))
# inner functions definition
def del_mult(tk, start, step):
for k in range(start, len(tk), step):
tk[k] = False
# end of inner functions definition
cpos = const * pos
while prime < stop:
# 30k + 7
if tk7[pos]:
prime = cpos + 7
p.append(prime)
lastadded = 7
for off in offsets:
tmp = d[(7, off)]
start = (
(pos + prime)
if off == 7
else (prime * (const * (pos + 1 if tmp < 7 else 0) + tmp)) // const
)
del_mult(tmptk[off], start, prime)
# 30k + 11
if tk11[pos]:
prime = cpos + 11
p.append(prime)
lastadded = 11
for off in offsets:
tmp = d[(11, off)]
start = (
(pos + prime)
if off == 11
else (prime * (const * (pos + 1 if tmp < 11 else 0) + tmp)) // const
)
del_mult(tmptk[off], start, prime)
# 30k + 13
if tk13[pos]:
prime = cpos + 13
p.append(prime)
lastadded = 13
for off in offsets:
tmp = d[(13, off)]
start = (
(pos + prime)
if off == 13
else (prime * (const * (pos + 1 if tmp < 13 else 0) + tmp)) // const
)
del_mult(tmptk[off], start, prime)
# 30k + 17
if tk17[pos]:
prime = cpos + 17
p.append(prime)
lastadded = 17
for off in offsets:
tmp = d[(17, off)]
start = (
(pos + prime)
if off == 17
else (prime * (const * (pos + 1 if tmp < 17 else 0) + tmp)) // const
)
del_mult(tmptk[off], start, prime)
# 30k + 19
if tk19[pos]:
prime = cpos + 19
p.append(prime)
lastadded = 19
for off in offsets:
tmp = d[(19, off)]
start = (
(pos + prime)
if off == 19
else (prime * (const * (pos + 1 if tmp < 19 else 0) + tmp)) // const
)
del_mult(tmptk[off], start, prime)
# 30k + 23
if tk23[pos]:
prime = cpos + 23
p.append(prime)
lastadded = 23
for off in offsets:
tmp = d[(23, off)]
start = (
(pos + prime)
if off == 23
else (prime * (const * (pos + 1 if tmp < 23 else 0) + tmp)) // const
)
del_mult(tmptk[off], start, prime)
# 30k + 29
if tk29[pos]:
prime = cpos + 29
p.append(prime)
lastadded = 29
for off in offsets:
tmp = d[(29, off)]
start = (
(pos + prime)
if off == 29
else (prime * (const * (pos + 1 if tmp < 29 else 0) + tmp)) // const
)
del_mult(tmptk[off], start, prime)
# now we go back to top tk1, so we need to increase pos by 1
pos += 1
cpos = const * pos
# 30k + 1
if tk1[pos]:
prime = cpos + 1
p.append(prime)
lastadded = 1
for off in offsets:
tmp = d[(1, off)]
start = (
(pos + prime)
if off == 1
else (prime * (const * pos + tmp)) // const
)
del_mult(tmptk[off], start, prime)
# time to add remaining primes
# if lastadded == 1, remove last element and start adding them from tk1
# this way we don't need an "if" within the last while
if lastadded == 1:
p.pop()
# now complete for every other possible prime
while pos < len(tk1):
cpos = const * pos
if tk1[pos]:
p.append(cpos + 1)
if tk7[pos]:
p.append(cpos + 7)
if tk11[pos]:
p.append(cpos + 11)
if tk13[pos]:
p.append(cpos + 13)
if tk17[pos]:
p.append(cpos + 17)
if tk19[pos]:
p.append(cpos + 19)
if tk23[pos]:
p.append(cpos + 23)
if tk29[pos]:
p.append(cpos + 29)
pos += 1
# remove exceeding if present
pos = len(p) - 1
while p[pos] > N:
pos -= 1
if pos < len(p) - 1:
del p[pos + 1 :]
# return p list
return p
def sieve_of_eratosthenes(n):
"""sieveOfEratosthenes(n): return the list of the primes < n."""
# Code from: <dickinsm@gmail.com>, Nov 30 2006
# http://groups.google.com/group/comp.lang.python/msg/f1f10ced88c68c2d
if n <= 2:
return []
sieve = list(range(3, n, 2))
top = len(sieve)
for si in sieve:
if si:
bottom = (si * si - 3) // 2
if bottom >= top:
break
sieve[bottom::si] = [0] * -((bottom - top) // si)
return [2] + [el for el in sieve if el]
def sieve_of_atkin(end):
"""return a list of all the prime numbers <end using the Sieve of Atkin."""
# Code by Steve Krenzel, <Sgk284@gmail.com>, improved
# Code: https://web.archive.org/web/20080324064651/http://krenzel.info/?p=83
# Info: http://en.wikipedia.org/wiki/Sieve_of_Atkin
assert end > 0
lng = (end - 1) // 2
sieve = [False] * (lng + 1)
x_max, x2, xd = int(sqrt((end - 1) / 4.0)), 0, 4
for xd in range(4, 8 * x_max + 2, 8):
x2 += xd
y_max = int(sqrt(end - x2))
n, n_diff = x2 + y_max * y_max, (y_max << 1) - 1
if not (n & 1):
n -= n_diff
n_diff -= 2
for d in range((n_diff - 1) << 1, -1, -8):
m = n % 12
if m == 1 or m == 5:
m = n >> 1
sieve[m] = not sieve[m]
n -= d
x_max, x2, xd = int(sqrt((end - 1) / 3.0)), 0, 3
for xd in range(3, 6 * x_max + 2, 6):
x2 += xd
y_max = int(sqrt(end - x2))
n, n_diff = x2 + y_max * y_max, (y_max << 1) - 1
if not (n & 1):
n -= n_diff
n_diff -= 2
for d in range((n_diff - 1) << 1, -1, -8):
if n % 12 == 7:
m = n >> 1
sieve[m] = not sieve[m]
n -= d
x_max, y_min, x2, xd = int((2 + sqrt(4 - 8 * (1 - end))) / 4), -1, 0, 3
for x in range(1, x_max + 1):
x2 += xd
xd += 6
if x2 >= end:
y_min = (((int(ceil(sqrt(x2 - end))) - 1) << 1) - 2) << 1
n, n_diff = ((x * x + x) << 1) - 1, (((x - 1) << 1) - 2) << 1
for d in range(n_diff, y_min, -8):
if n % 12 == 11:
m = n >> 1
sieve[m] = not sieve[m]
n += d
primes = [2, 3]
if end <= 3:
return primes[: max(0, end - 2)]
for n in range(5 >> 1, (int(sqrt(end)) + 1) >> 1):
if sieve[n]:
primes.append((n << 1) + 1)
aux = (n << 1) + 1
aux *= aux
for k in range(aux, end, 2 * aux):
sieve[k >> 1] = False
s = int(sqrt(end)) + 1
if s % 2 == 0:
s += 1
primes.extend([i for i in range(s, end, 2) if sieve[i >> 1]])
return primes
def ambi_sieve_plain(n):
s = list(range(3, n, 2))
for m in range(3, int(n ** 0.5) + 1, 2):
if s[(m - 3) // 2]:
for t in range((m * m - 3) // 2, (n >> 1) - 1, m):
s[t] = 0
return [2] + [t for t in s if t > 0]
def sundaram3(max_n):
# https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/2073279#2073279
numbers = range(3, max_n + 1, 2)
half = (max_n) // 2
initial = 4
for step in range(3, max_n + 1, 2):
for i in range(initial, half, step):
numbers[i - 1] = 0
initial += 2 * (step + 1)
if initial > half:
return [2] + filter(None, numbers)
# Using Numpy:
def ambi_sieve(n):
# http://tommih.blogspot.com/2009/04/fast-prime-number-generator.html
s = np.arange(3, n, 2)
for m in range(3, int(n ** 0.5) + 1, 2):
if s[(m - 3) // 2]:
s[(m * m - 3) // 2::m] = 0
return np.r_[2, s[s > 0]]
def primesfrom3to(n):
# https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Returns an array of primes, p < n """
assert n >= 2
sieve = np.ones(n // 2, dtype=bool)
for i in range(3, int(n ** 0.5) + 1, 2):
if sieve[i // 2]:
sieve[i * i // 2::i] = False
return np.r_[2, 2 * np.nonzero(sieve)[0][1::] + 1]
def primesfrom2to(n):
# https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Input n>=6, Returns an array of primes, 2 <= p < n """
assert n >= 6
sieve = np.ones(n // 3 + (n % 6 == 2), dtype=bool)
sieve[0] = False
for i in range(int(n ** 0.5) // 3 + 1):
if sieve[i]:
k = 3 * i + 1 | 1
sieve[((k * k) // 3)::2 * k] = False
sieve[(k * k + 4 * k - 2 * k * (i & 1)) // 3::2 * k] = False
return np.r_[2, 3, ((3 * np.nonzero(sieve)[0] + 1) | 1)]
def sympy_sieve(n):
return list(sympy.sieve.primerange(1, n))
b = perfplot.bench(
setup=lambda n: n,
kernels=[
rwh_primes,
rwh_primes1,
rwh_primes2,
sieve_wheel_30,
sieve_of_eratosthenes,
sieve_of_atkin,
# ambi_sieve_plain,
# sundaram3,
ambi_sieve,
primesfrom3to,
primesfrom2to,
sympy_sieve,
],
n_range=[2 ** k for k in range(3, 25)],
xlabel="n",
)
b.save("out.png")
b.show()
N을 제어할 수 있는 경우 모든 소수를 나열하는 가장 빠른 방법은 소수를 미리 계산하는 것입니다.정말이에요.프리컴퓨팅은 간과된 최적화입니다.
Python에서 prime를 생성할 때 사용하는 코드는 다음과 같습니다.
$ 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)
여기에 게재되어 있는 보다 빠른 솔루션과는 비교가 되지 않지만, 적어도 순수한 비단뱀입니다.
이 질문을 올려주셔서 감사합니다.오늘 정말 많이 배웠어요.
Numpy를 사용한 하프 체의 약간 다른 구현:
수학을 가져오다Import numpydef prime6(최고): primes=numpy.arange(3, 최대+1,2)isprime=numpy.ones((최대-1)/2, dtype=bool)소수[:int(math.sqrt(upto)] 인자의 경우: if isprime[(factor-2)/2]: isprime[(factor*3-2)/2:(upto-1)/2:factor]=0numpy.insert(소수[isprime],0,2를 반환합니다.
누가 이걸 다른 타이밍과 비교할 수 있나요?내 기계에서 그것은 다른 Numpy 반 시브와 꽤 비슷해 보인다.
다 쓰여져 있고 테스트도 되어 있어요.따라서 바퀴를 재창조할 필요가 없습니다.
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밀리초라고 기재되어 있습니다.이것 좀 봐!!!
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
N < 9,080,191이라는 가정에 대한 Miller-Rabin's Primality 검정의 결정론적 구현
import sys
def miller_rabin_pass(a, n):
d = n - 1
s = 0
while d % 2 == 0:
d >>= 1
s += 1
a_to_power = pow(a, d, n)
if a_to_power == 1:
return True
for i in range(s-1):
if a_to_power == n - 1:
return True
a_to_power = (a_to_power * a_to_power) % n
return a_to_power == n - 1
def miller_rabin(n):
if n <= 2:
return n == 2
if n < 2_047:
return miller_rabin_pass(2, n)
return all(miller_rabin_pass(a, n) for a in (31, 73))
n = int(sys.argv[1])
primes = [2]
for p in range(3,n,2):
if miller_rabin(p):
primes.append(p)
print len(primes)
위키피디아(http://en.wikipedia.org/wiki/Miller-Rabin_primality_test) 기사에 따르면, n < 9,080,191의 a = 37과 73에 대한 테스트는 N이 복합인지 아닌지를 결정하기에 충분하다.
그리고 나는 여기에서 발견된 원래의 Miller-Rabin의 테스트의 확률론적 구현에서 소스 코드를 수정했다: https://www.literateprograms.org/miller-rabin_primality_test__python_.html
가장 빠른 코드에는 numpy 솔루션이 가장 좋습니다.다만 순수하게 학구적인 이유로 Python 버전을 올렸습니다.이것은 위에 게재된 요리책 버전보다 50% 이상 빠른 속도입니다.리스트 전체를 메모리로 만들기 때문에 모든 것을 담을 수 있는 충분한 공간이 필요하지만, 꽤 잘 확장할 수 있을 것 같습니다.
def daniel_sieve_2(maxNumber):
"""
Given a number, returns all numbers less than or equal to
that number which are prime.
"""
allNumbers = range(3, maxNumber+1, 2)
for mIndex, number in enumerate(xrange(3, maxNumber+1, 2)):
if allNumbers[mIndex] == 0:
continue
# now set all multiples to 0
for index in xrange(mIndex+number, (maxNumber-3)/2+1, number):
allNumbers[index] = 0
return [2] + filter(lambda n: n!=0, allNumbers)
그 결과:
>>>mine = timeit.Timer("daniel_sieve_2(1000000)",
... "from sieves import daniel_sieve_2")
>>>prev = timeit.Timer("get_primes_erat(1000000)",
... "from sieves import get_primes_erat")
>>>print "Mine: {0:0.4f} ms".format(min(mine.repeat(3, 1))*1000)
Mine: 428.9446 ms
>>>print "Previous Best {0:0.4f} ms".format(min(prev.repeat(3, 1))*1000)
Previous Best 621.3581 ms
대회가 몇 년 동안 닫혀 있다는 걸 알아요.…
그럼에도 불구하고, 이것은 체를 앞으로 처리할 때 적절한 단계를 사용하여 2, 3, 5의 배수를 생략한 것을 바탕으로 한 순수한 python prime 체에 대한 나의 제안이다.그러나 실제로는 N<10^9의 경우 @Robert William Hanks의 우수한 솔루션 rwh_primes2 및 rwh_primes1보다 느립니다.ctype을 사용합니다.1.5* 10^8 이상의 c_ushort 체 배열은 메모리 한계에 적응합니다.
10^6
$ python - mtimeit - s " import prime Sieve Speed Comp " " prime Sieve Speed Comp . prime Sieve Seq ( 1000000)" 10루프, 베스트 3: 46.7밀리초/루프
비교 대상: $ python - mtimeit - s" import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes1(100000000)" 10루프, 비교 대상: $python - mtimeit - s" "primeVeSpeedComp" (1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
10^7
$ python - mtimeit - s " import prime Sieve Speed Comp " " prime Sieve Speed Comp . prime Sieve Seq ( 10000000 ) 10루프, 베스트 3: 530밀리초/루프
비교 대상: $ python - mtimeit - s" import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes1(100000000)" 10루프, 비교 대상: $ python - m timeit - s" " primeveSpeedComp" "PrimeveSpeed1(1000000000000000)"
10^8
$ python - mtimeit - s " import prime Sieve Speed Comp " " prime Sieve Speed Comp . prime Sieve Seq ( 100000000)" 10루프, 루프당 베스트 3: 5.55초
비교 대상: $python - mtimeit - s"import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes1(10000000000)" 10루프, 비교 대상: $python - m timeit - s" "PrimeveSpeedComp" (10000000000000000000000)
10^9
$ python - mtimeit - s " import prime Sieve Speed Comp " " prime Sieve Speed Comp . prime Sieve Seq ( 1000000000 ) 10루프, 루프당 베스트 3: 61.2초
비교 대상: $ python - mtimeit - n 3 - s " import prime Sieve Speed Comp . rwh _ primes 1 ( 1000000000 )" 루프 3개, 루프당 최대 3: 97.8초
비교 대상: $ python - m timeit - s " import prime Sieve Speed Comp . rwh _ primes 2 ( 1000000000 )" 루프 10개, 루프당 베스트3: 41.9초
아래 코드를 ubuntus primeSieveSpeedComp에 복사하여 이 테스트를 검토할 수 있습니다.
def primeSieveSeq(MAX_Int):
if MAX_Int > 5*10**8:
import ctypes
int16Array = ctypes.c_ushort * (MAX_Int >> 1)
sieve = int16Array()
#print 'uses ctypes "unsigned short int Array"'
else:
sieve = (MAX_Int >> 1) * [False]
#print 'uses python list() of long long int'
if MAX_Int < 10**8:
sieve[4::3] = [True]*((MAX_Int - 8)/6+1)
sieve[12::5] = [True]*((MAX_Int - 24)/10+1)
r = [2, 3, 5]
n = 0
for i in xrange(int(MAX_Int**0.5)/30+1):
n += 3
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
n += 2
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
n += 1
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
n += 2
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
n += 1
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
n += 2
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
n += 3
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
n += 1
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
if MAX_Int < 10**8:
return [2, 3, 5]+[(p << 1) + 1 for p in [n for n in xrange(3, MAX_Int >> 1) if not sieve[n]]]
n = n >> 1
try:
for i in xrange((MAX_Int-2*n)/30 + 1):
n += 3
if not sieve[n]:
r.append((n << 1) + 1)
n += 2
if not sieve[n]:
r.append((n << 1) + 1)
n += 1
if not sieve[n]:
r.append((n << 1) + 1)
n += 2
if not sieve[n]:
r.append((n << 1) + 1)
n += 1
if not sieve[n]:
r.append((n << 1) + 1)
n += 2
if not sieve[n]:
r.append((n << 1) + 1)
n += 3
if not sieve[n]:
r.append((n << 1) + 1)
n += 1
if not sieve[n]:
r.append((n << 1) + 1)
except:
pass
return r
나는 몇 개의 unutbu의 함수를 테스트했고, 나는 그것을 굶주린 수백만 개의 숫자로 계산했다.
수상자는 numpy 라이브러리를 사용하는 기능,
메모: 메모리 사용률 테스트도 실시합니다.
샘플코드
#!/usr/bin/env python
import lib
import timeit
import sys
import math
import datetime
import prettyplotlib as ppl
import numpy as np
import matplotlib.pyplot as plt
from prettyplotlib import brewer2mpl
primenumbers_gen = [
'sieveOfEratosthenes',
'ambi_sieve',
'ambi_sieve_plain',
'sundaram3',
'sieve_wheel_30',
'primesfrom3to',
'primesfrom2to',
'rwh_primes',
'rwh_primes1',
'rwh_primes2',
]
def human_format(num):
# https://stackoverflow.com/questions/579310/formatting-long-numbers-as-strings-in-python?answertab=active#tab-top
magnitude = 0
while abs(num) >= 1000:
magnitude += 1
num /= 1000.0
# add more suffixes if you need them
return '%.2f%s' % (num, ['', 'K', 'M', 'G', 'T', 'P'][magnitude])
if __name__=='__main__':
# Vars
n = 10000000 # number itereration generator
nbcol = 5 # For decompose prime number generator
nb_benchloop = 3 # Eliminate false positive value during the test (bench average time)
datetimeformat = '%Y-%m-%d %H:%M:%S.%f'
config = 'from __main__ import n; import lib'
primenumbers_gen = {
'sieveOfEratosthenes': {'color': 'b'},
'ambi_sieve': {'color': 'b'},
'ambi_sieve_plain': {'color': 'b'},
'sundaram3': {'color': 'b'},
'sieve_wheel_30': {'color': 'b'},
# # # 'primesfrom2to': {'color': 'b'},
'primesfrom3to': {'color': 'b'},
# 'rwh_primes': {'color': 'b'},
# 'rwh_primes1': {'color': 'b'},
'rwh_primes2': {'color': 'b'},
}
# Get n in command line
if len(sys.argv)>1:
n = int(sys.argv[1])
step = int(math.ceil(n / float(nbcol)))
nbs = np.array([i * step for i in range(1, int(nbcol) + 1)])
set2 = brewer2mpl.get_map('Paired', 'qualitative', 12).mpl_colors
print datetime.datetime.now().strftime(datetimeformat)
print("Compute prime number to %(n)s" % locals())
print("")
results = dict()
for pgen in primenumbers_gen:
results[pgen] = dict()
benchtimes = list()
for n in nbs:
t = timeit.Timer("lib.%(pgen)s(n)" % locals(), setup=config)
execute_times = t.repeat(repeat=nb_benchloop,number=1)
benchtime = np.mean(execute_times)
benchtimes.append(benchtime)
results[pgen] = {'benchtimes':np.array(benchtimes)}
fig, ax = plt.subplots(1)
plt.ylabel('Computation time (in second)')
plt.xlabel('Numbers computed')
i = 0
for pgen in primenumbers_gen:
bench = results[pgen]['benchtimes']
avgs = np.divide(bench,nbs)
avg = np.average(bench, weights=nbs)
# Compute linear regression
A = np.vstack([nbs, np.ones(len(nbs))]).T
a, b = np.linalg.lstsq(A, nbs*avgs)[0]
# Plot
i += 1
#label="%(pgen)s" % locals()
#ppl.plot(nbs, nbs*avgs, label=label, lw=1, linestyle='--', color=set2[i % 12])
label="%(pgen)s avg" % locals()
ppl.plot(nbs, a * nbs + b, label=label, lw=2, color=set2[i % 12])
print datetime.datetime.now().strftime(datetimeformat)
ppl.legend(ax, loc='upper left', ncol=4)
# Change x axis label
ax.get_xaxis().get_major_formatter().set_scientific(False)
fig.canvas.draw()
labels = [human_format(int(item.get_text())) for item in ax.get_xticklabels()]
ax.set_xticklabels(labels)
ax = plt.gca()
plt.show()
Python 3의 경우
def rwh_primes2(n):
correction = (n%6>1)
n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
sieve = [True] * (n//3)
sieve[0] = False
for i in range(int(n**0.5)//3+1):
if sieve[i]:
k=3*i+1|1
sieve[ ((k*k)//3) ::2*k]=[False]*((n//6-(k*k)//6-1)//k+1)
sieve[(k*k+4*k-2*k*(i&1))//3::2*k]=[False]*((n//6-(k*k+4*k-2*k*(i&1))//6-1)//k+1)
return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]
아직 아무도 언급하지 않았다니 놀랍네요.
이 버전은 2.47ms ± 36.5µs로 1M에 도달합니다.
수년 전, 위키피디아 페이지 프라임 넘버에 앳킨 체 버전의 유사 코드가 제공되었습니다.이것은 더 이상 존재하지 않으며, Sheve of Atkin에 대한 참조는 다른 알고리즘인 것 같습니다.2007/03/01 버전의 Wikipedia 페이지인 2007-03-01 현재 Primer number에는 제가 참조로 사용한 의사 코드가 나와 있습니다.
import numpy as np
from numba import njit
@njit
def nb_primes(n):
# Generates prime numbers 2 <= p <= n
# Atkin's sieve -- see https://en.wikipedia.org/w/index.php?title=Prime_number&oldid=111775466
sqrt_n = int(np.sqrt(n)) + 1
# initialize the sieve
s = np.full(n + 1, -1, dtype=np.int8)
s[2] = 1
s[3] = 1
# put in candidate primes:
# integers which have an odd number of
# representations by certain quadratic forms
for x in range(1, sqrt_n):
x2 = x * x
for y in range(1, sqrt_n):
y2 = y * y
k = 4 * x2 + y2
if k <= n and (k % 12 == 1 or k % 12 == 5): s[k] *= -1
k = 3 * x2 + y2
if k <= n and (k % 12 == 7): s[k] *= -1
k = 3 * x2 - y2
if k <= n and x > y and k % 12 == 11: s[k] *= -1
# eliminate composites by sieving
for k in range(5, sqrt_n):
if s[k]:
k2 = k*k
# k is prime, omit multiples of its square; this is sufficient because
# composites which managed to get on the list cannot be square-free
for i in range(1, n // k2 + 1):
j = i * k2 # j ∈ {k², 2k², 3k², ..., n}
s[j] = -1
return np.nonzero(s>0)[0]
# initial run for "compilation"
nb_primes(10)
타이밍.
In[10]:
%timeit nb_primes(1_000_000)
Out[10]:
2.47 ms ± 36.5 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In[11]:
%timeit nb_primes(10_000_000)
Out[11]:
33.4 ms ± 373 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
In[12]:
%timeit nb_primes(100_000_000)
Out[12]:
828 ms ± 5.64 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
python을 처음 사용하는 것이기 때문에 사용하는 방법 중에는 조금 번거로운 것이 있을 수 있습니다.방금 c++ 코드를 python으로 변환했습니다만, 이것이 제가 가지고 있는 것입니다(python에서는 조금 느리지만).
#!/usr/bin/env python
import time
def GetPrimes(n):
Sieve = [1 for x in xrange(n)]
Done = False
w = 3
while not Done:
for q in xrange (3, n, 2):
Prod = w*q
if Prod < n:
Sieve[Prod] = 0
else:
break
if w > (n/2):
Done = True
w += 2
return Sieve
start = time.clock()
d = 10000000
Primes = GetPrimes(d)
count = 1 #This is for 2
for x in xrange (3, d, 2):
if Primes[x]:
count+=1
elapsed = (time.clock() - start)
print "\nFound", count, "primes in", elapsed, "seconds!\n"
pythonw 프라임즈화이
12.799119초만에 664579 소수점 발견!
#!/usr/bin/env python
import time
def GetPrimes2(n):
Sieve = [1 for x in xrange(n)]
for q in xrange (3, n, 2):
k = q
for y in xrange(k*3, n, k*2):
Sieve[y] = 0
return Sieve
start = time.clock()
d = 10000000
Primes = GetPrimes2(d)
count = 1 #This is for 2
for x in xrange (3, d, 2):
if Primes[x]:
count+=1
elapsed = (time.clock() - start)
print "\nFound", count, "primes in", elapsed, "seconds!\n"
pythonw Primes2.화이
10.230172초 만에 664579 소수점을 찾았습니다!
#!/usr/bin/env python
import time
def GetPrimes3(n):
Sieve = [1 for x in xrange(n)]
for q in xrange (3, n, 2):
k = q
for y in xrange(k*k, n, k << 1):
Sieve[y] = 0
return Sieve
start = time.clock()
d = 10000000
Primes = GetPrimes3(d)
count = 1 #This is for 2
for x in xrange (3, d, 2):
if Primes[x]:
count+=1
elapsed = (time.clock() - start)
print "\nFound", count, "primes in", elapsed, "seconds!\n"
python primes2.화이
7.113776초 만에 64579 소수점을 찾았습니다!
가장 간단한 방법은 다음과 같습니다.
primes = []
for n in range(low, high + 1):
if all(n % i for i in primes):
primes.append(n)
내 생각엔 가장 빠른 방법은 코드의 소수점을 하드코드로 만드는 거야
따라서 모든 번호가 유선 연결된 다른 소스 파일을 생성하는 느린 스크립트를 작성하여 실제 프로그램을 실행할 때 해당 소스 파일을 Import하면 됩니다.
물론 이것은 컴파일 시에 N의 상한을 알고 있는 경우에만 유효하지만, 따라서 (거의) 모든 프로젝트 오일러 문제에 해당됩니다.
PS: 수 , 한 된 Python에서 됩니다..pyc이 경우 모든 소수점 이하가 N인 바이너리 배열을 읽는 것은 매우 빠릅니다.
번거로우시겠지만 erat2()는 알고리즘에 심각한 결함이 있습니다.
다음 컴포지트를 검색할 때는 홀수만 테스트해야 합니다.q, p는 둘 다 홀수입니다.그러면 q+p는 짝수이고 테스트할 필요가 없지만 q+2*p는 항상 홀수입니다.그러면 while loop 조건의 if equal 테스트가 없어지고 런타임의 약 30%가 절약됩니다.
이왕이면: 우아한 'D.pop(q,None)' get and delete 메서드 대신 'if q in D: p=D[q], del D[q]'를 사용합니다.이것은 2배의 속도입니다.적어도 내 기계(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
파티에 늦을 수도 있지만, 이것을 위해 나만의 코드를 추가해야 합니다.짝수를 저장할 필요가 없고 비트어레이 파이썬 모듈을 사용하여 메모리 소비를 줄이고 최대 100억까지 모든 소수를 계산할 수 있기 때문에 약 2분의 1의 공간을 사용합니다.
from bitarray import bitarray
def primes_to(n):
size = n//2
sieve = bitarray(size)
sieve.setall(1)
limit = int(n**0.5)
for i in range(1,limit):
if sieve[i]:
val = 2*i+1
sieve[(i+i*val)::val] = 0
return [2] + [2*i+1 for i, v in enumerate(sieve) if v and i > 0]
python -m timeit -n10 -s "import euler" "euler.primes_to(1000000000)"
10 loops, best of 3: 46.5 sec per loop
이것은 64비트 2.4에서 실행되었습니다.GHZ MAC OSX 10.8.3
복잡도(길이 n의 배열 정렬보다 낮음)와 벡터화를 모두 가지는 Eratostenes의 Sheve의 numpy 버전.@unutbu의 곱셈과 비교하면 100만 미만의 모든 소수를 찾기 위해 46개의 마이크로세콘이 포함된 패키지와 같은 속도입니다.
import numpy as np
def generate_primes(n):
is_prime = np.ones(n+1,dtype=bool)
is_prime[0:2] = False
for i in range(int(n**0.5)+1):
if is_prime[i]:
is_prime[i**2::i]=False
return np.where(is_prime)[0]
타이밍:
import time
for i in range(2,10):
timer =time.time()
generate_primes(10**i)
print('n = 10^',i,' time =', round(time.time()-timer,6))
>> n = 10^ 2 time = 5.6e-05
>> n = 10^ 3 time = 6.4e-05
>> n = 10^ 4 time = 0.000114
>> n = 10^ 5 time = 0.000593
>> n = 10^ 6 time = 0.00467
>> n = 10^ 7 time = 0.177758
>> n = 10^ 8 time = 1.701312
>> n = 10^ 9 time = 19.322478
다음은 파이썬의 목록 정보를 사용하여 소수(가장 효율적이지 않음)를 생성하는 흥미로운 기술입니다.
noprimes = [j for i in range(2, 8) for j in range(i*2, 50, i)]
primes = [x for x in range(2, 50) if x not in noprimes]
(늦은) 기사에 의하면, 이 솔루션은 투고된 솔루션 중 가장 빨리 동작하고 있습니다(적어도 제 머신에 있습니다).모두 하며 numpy bitarray에서 영감을 .또한 이 기능은primesfrom2to이 대답에서.
import numpy as np
from bitarray import bitarray
def bit_primes(n):
bit_sieve = bitarray(n // 3 + (n % 6 == 2))
bit_sieve.setall(1)
bit_sieve[0] = False
for i in range(int(n ** 0.5) // 3 + 1):
if bit_sieve[i]:
k = 3 * i + 1 | 1
bit_sieve[k * k // 3::2 * k] = False
bit_sieve[(k * k + 4 * k - 2 * k * (i & 1)) // 3::2 * k] = False
np_sieve = np.unpackbits(np.frombuffer(bit_sieve.tobytes(), dtype=np.uint8)).view(bool)
return np.concatenate(((2, 3), ((3 * np.flatnonzero(np_sieve) + 1) | 1)))
가 있습니다.primesfrom2to이 솔루션은 이전에 unutbu의 비교에서 가장 빠른 솔루션으로 판명되었습니다.
python3 -m timeit -s "import fast_primes" "fast_primes.bit_primes(1000000)"
200 loops, best of 5: 1.19 msec per loop
python3 -m timeit -s "import fast_primes" "fast_primes.primesfrom2to(1000000)"
200 loops, best of 5: 1.23 msec per loop
을 찾는 , 100은 100으로 지정됩니다.bit_primes값이 큰 경우n네, 그렇습니다., 「」라고 하는 경우도 있습니다.bit_primes: 2배 이상 빨랐습니다.
python3 -m timeit -s "import fast_primes" "fast_primes.bit_primes(500_000_000)"
1 loop, best of 5: 540 msec per loop
python3 -m timeit -s "import fast_primes" "fast_primes.primesfrom2to(500_000_000)"
1 loop, best of 5: 1.15 sec per loop
수정 인 (Python 3에서 작동하도록) Python 3에서 하도록 수정한편, (Python 3에서 작동)primesfrom2to교교: :
def primesfrom2to(n):
# https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Input n>=6, Returns a array of primes, 2 <= p < n"""
sieve = np.ones(n // 3 + (n % 6 == 2), dtype=np.bool)
sieve[0] = False
for i in range(int(n ** 0.5) // 3 + 1):
if sieve[i]:
k = 3 * i + 1 | 1
sieve[((k * k) // 3)::2 * k] = False
sieve[(k * k + 4 * k - 2 * k * (i & 1)) // 3::2 * k] = False
return np.r_[2, 3, ((3 * np.nonzero(sieve)[0] + 1) | 1)]
언급URL : https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n
'source' 카테고리의 다른 글
| 함수에서 키워드 사용 - PHP (0) | 2022.10.15 |
|---|---|
| openssl_encrypt에서의 초기화 벡터 사용 (0) | 2022.10.14 |
| INSERT SELECT와 함께 재귀 CTE를 사용하여 Maria와 함께 테이블 데이터 생성DB (0) | 2022.10.14 |
| 데몬 프로세스로 php 스크립트 실행 (0) | 2022.10.14 |
| 각 열에 대해 가장 일반적인 값을 가져옵니다. (0) | 2022.10.14 |