반응형
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
더 빠르게 만들 수 있습니까?
이 코드에는 결함 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
경고 : timeit 하드웨어 또는 Python 버전의 차이로 인해 결과가 달라질 수 있습니다.
다음은 여러 구현을 비교하는 스크립트입니다.
- ambi_sieve_plain,
- rwh_primes ,
- rwh_primes1 ,
- rwh_primes2 ,
- sieveOfAtkin ,
- sieveOfEratosthenes ,
- sundaram3 ,
- sieve_wheel_30 ,
- ambi_sieve (numpy 필요)
- 소수부터 3까지 (numpy 필요)
- 소수부터 2까지 (numpy 필요)
많은 감사합니다 스테판 내 관심에 sieve_wheel_30을 가져 위해. 크레딧은 Robert William Hanks 에게 2부터 소수까지, 소수부터 3까지, rwh_primes, rwh_primes1 및 rwh_primes2로갑니다.
psyco 로 n = 1000000에 대해 테스트 된 일반 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 = 1000000에 대해 테스트 된 일반 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 = 1000000에 대해 numpy를 허용 하는 테스트 된 모든 방법 중에서 primesfrom2to 가 가장 빠른 테스트를 거쳤습니다.
+---------------------+-------+
| 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)
스크립트를 실행하면 모든 구현이 동일한 결과를 제공합니다.
더 빠르고 더 메모리 방식의 순수한 파이썬 코드 :
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]]
더 빠르고 메모리가 많은 숫자 코드 :
import numpy
def primesfrom3to(n):
""" Returns a array of primes, 3 <= p < n """
sieve = numpy.ones(n//2, dtype=numpy.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=numpy.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 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
Cookbook 솔루션의 속도가 두 배 이상 빠릅니다.
Sundaram 's Sieve를 사용하여 순수 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)
비교 :
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]
경우 N > primes[-1] 에만 다음 더 소수를 계산하고, 코드에서 그래서 다음 번에 새 목록을 저장 그것은 빨리 동등하다.
항상 상자 밖에서 생각하십시오.
휠을 재발 명하지 않으려면 기호 수학 라이브러리 sympy를 설치하면 됩니다 (예 : Python 3 호환).
pip install sympy
프라임 범위 기능을 사용하십시오.
from sympy import sieve
primes = list(sieve.primerange(1, 10**6))
itertools를 허용하지만 numpy는 허용하지 않는 경우 다음은 내 컴퓨터에서 약 두 배 빠르게 실행되는 Python 3에 대한 rwh_primes2의 적응입니다. 유일한 실질적인 변화는 부울 목록 대신 바이트 배열을 사용하고 최종 목록을 작성하기 위해 목록 이해 대신 압축을 사용하는 것입니다. (가능한 경우 moarningsun과 같은 의견으로 이것을 추가하고 싶습니다.)
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
자신의 주요 발견 코드를 작성하는 것이 도움이되지만 빠르고 안정적인 라이브러리를 보유하는 것도 유용합니다. 나는 래퍼 썼다 라이브러리 primesieve ++ C를 이 이름, primesieve - 파이썬
시도 해봐 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:])]
N <9,080,191이라는 가정에 대한 Miller-Rabin의 원시성 테스트의 결정적 구현
import sys
import random
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 xrange(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):
for a in [2, 3, 37, 73]:
if not miller_rabin_pass(a, n):
return False
return True
n = int(sys.argv[1])
primes = [2]
for p in range(3,n,2):
if miller_rabin(p):
primes.append(p)
print len(primes)
Wikipedia ( http://en.wikipedia.org/wiki/Miller–Rabin_primality_test ) 테스트 기사에 따르면 N = 9,080,191 a = 2,3,37, 73은 N이 복합인지 아닌지를 결정하기에 충분합니다.
그리고 원래의 Miller-Rabin 테스트의 확률 적 구현에서 소스 코드를 수정했습니다 : http://en.literateprograms.org/Miller-Rabin_primality_test_(Python)
N을 제어 할 수있는 경우 모든 소수를 나열하는 가장 빠른 방법은 소수를 사전 계산하는 것입니다. 진심으로. 사전 계산은 간과 된 최적화 방법입니다.
파이썬에서 소수를 생성하는 데 일반적으로 사용하는 코드는 다음과 같습니다.
$ 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 솔루션이 가장 좋습니다. 순수한 학문적 인 이유로, 나는 순수한 파이썬 버전을 게시하고 있는데, 이는 위에 게시 된 요리 책 버전보다 약간 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
Numpy를 사용하는 반 체의 약간 다른 구현 :
수학 가져 오기
numpy 가져 오기
데프 프라임 6 (최대) :
소수 = numpy.arange (3, 최대 +1,2)
isprime = numpy.ones ((최대 1) / 2, dtype = bool)
소인수에 대한 값 [: int (math.sqrt (upto))] :
isprime [(factor-2) / 2] 인 경우 : isprime [(factor * 3-2) / 2 :( 최대 -1) / 2 : factor] = 0
numpy.insert (primes [isprime], 0,2)를 리턴하십시오.
누군가 이것을 다른 타이밍과 비교할 수 있습니까? 내 컴퓨터에서는 다른 Numpy half-sieve와 상당히 비슷해 보입니다.
모두 작성되고 테스트되었습니다. 따라서 휠을 재발 명할 필요가 없습니다.
python -m timeit -r10 -s"from sympy import sieve" "primes = list(sieve.primerange(1, 10**6))"
우리에게 12.2 msec 의 기록을 breaking습니다 !
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 개의 up-votes에 대한 답변은 최상의 솔루션을위한 15.9ms를 나타냅니다. 이것을 비교하십시오 !!!
나는 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()
파이썬 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]]
처음으로 파이썬을 사용하기 때문에 여기에 사용하는 일부 방법이 약간 번거로울 수 있습니다. 방금 C ++ 코드를 파이썬으로 직접 변환했는데 이것이 내가 가지고있는 것입니다 (파이썬에서는 조금 느립니다)
#!/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 Primes.py
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.py
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"
파이썬 Primes2.py
7.113776 초 안에 664579 소수를 찾았습니다!
나는 경쟁이 몇 년 동안 끝났다는 것을 알고 있습니다. …
그럼에도 불구하고 이것은 체를 앞으로 처리하는 동안 적절한 단계를 사용하여 2, 3 및 5의 배수를 생략 한 순수한 파이썬 주요 체에 대한 나의 제안입니다. 그럼에도 불구하고 실제로 @Robert William Hanks의 우수한 솔루션 rwh_primes2 및 rwh_primes1보다 N <10 ^ 9의 경우 속도가 느립니다. 1.5 * 10 ^ 8 이상의 ctypes.c_ushort sieve 배열을 사용하면 메모리 제한에 적응할 수 있습니다.
10 ^ 6
$ python -mtimeit -s "import primeSieveSpeedComp" "primeSieveSpeedComp.primeSieveSeq (1000000)"10 개의 루프, 3 개 중 최고 : 36.7msec
$ python -mtimeit -s "import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes1 (1000000)"10 개의 루프, 루프 당 3 : 43.2msec의 최고 : $ python -m timeit -s "import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes2 (1000000) "10 루프, 루프 당 3 : 34.5 msec
10 ^ 7
$ python -mtimeit -s "import primeSieveSpeedComp" "primeSieveSpeedComp.primeSieveSeq (10000000)"10 개 루프, 루프 당 3 개 중 최대 : 530msec
$ python -mtimeit -s "import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes1 (10000000)"10 개의 루프, 루프 당 3 : 394msec의 최고 : $ python -m timeit -s "import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes2 (10000000) "10 루프, 루프 당 3 : 375msec 이하
10 ^ 8
$ python -mtimeit -s "import primeSieveSpeedComp" "primeSieveSpeedComp.primeSieveSeq (100000000)"10 루프, 루프 당 3:55 초 중 최고
$ python -mtimeit -s "import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes1 (100000000)"10 개의 루프, 루프 당 3 : 5 : 33 초 중 최고 : $ python -m timeit -s "import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes2 (100000000) "10 루프, 루프 당 3 : 3 초 최고
10 ^ 9
$ python -mtimeit -s "import primeSieveSpeedComp" "primeSieveSpeedComp.primeSieveSeq (1000000000)"10 개의 루프, 루프 당 3 : 61.2 초 중 최고
비교하려면 : $ python -mtimeit -n 3 -s "import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes1 (1000000000)"3 개의 루프, 루프 당 3 : 97.8 초 최고
비교 : $ python -m timeit -s "import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes2 (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
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의 배열을 정렬하는 것보다 낮음)와 벡터화를 모두 갖춘 수많은 버전의 에라토스테네스입니다. @unutbu와 비교했을 때 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
내 생각에 가장 빠른 방법은 코드에서 소수를 하드 코딩하는 것입니다.
따라서 모든 숫자가 고정 된 다른 소스 파일을 생성하는 느린 스크립트를 작성한 다음 실제 프로그램을 실행할 때 해당 소스 파일을 가져와야합니다.
물론 이것은 컴파일 타임에 N의 상한을 알고있는 경우에만 작동하지만 (거의) 모든 프로젝트 오일러 문제의 경우입니다.
추신 : 하드 와이어 된 프라임으로 소스를 파싱하는 것이 처음부터 소스를 계산하는 것보다 느리지 만 잘못 될 수 있지만, 파이썬이 컴파일 된 .pyc파일 에서 실행되는 것을 아는 한, N까지의 모든 프라임이있는 이진 배열을 읽는 것은 피의가되어야합니다 이 경우 빠릅니다.
귀찮게해서 죄송하지만 erat2 ()는 알고리즘에 심각한 결함이 있습니다.
다음 합성을 검색하는 동안 홀수 만 테스트하면됩니다. q, p 둘 다 홀수입니다. q + p는 짝수이며 테스트 할 필요는 없지만 q + 2 * p는 항상 홀수입니다. 이는 while 루프 조건에서 "짝수"테스트를 제거하고 런타임의 약 30 %를 절약합니다.
우리가 그 동안 : 우아한 'D.pop (q, None)'get 및 delete 메소드 대신 'if 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 요리 책erat2 함수를 기반으로합니다 .
import itertools as it
def erat2a( ):
D = { }
yield 2
for q in it.islice(it.count(3), 0, None, 2):
p = D.pop(q, None)
if p is None:
D[q*q] = q
yield q
else:
x = q + 2*p
while x in D:
x += 2*p
D[x] = p
속도 향상에 대한 설명은 이 답변을 참조하십시오 .
나는 파티에 늦을 수도 있지만 이것을 위해 내 자신의 코드를 추가해야 할 것입니다. 우리는 짝수를 저장할 필요가 없기 때문에 공간에서 약 n / 2를 사용하고 비트 배열 파이썬 모듈을 사용하여 메모리 소비를 크게 줄이고 최대 1,000,000,000까지 모든 소수를 계산할 수 있습니다
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.4GHZ MAC OSX 10.8.3에서 실행되었습니다.
시간이 지남에 따라 소수의 체를 수집했습니다. 내 컴퓨터에서 가장 빠른 것은 다음과 같습니다.
from time import time
# 175 ms for all the primes up to the value 10**6
def primes_sieve(limit):
a = [True] * limit
a[0] = a[1] = False
#a[2] = True
for n in xrange(4, limit, 2):
a[n] = False
root_limit = int(limit**.5)+1
for i in xrange(3,root_limit):
if a[i]:
for n in xrange(i*i, limit, 2*i):
a[n] = False
return a
LIMIT = 10**6
s=time()
primes = primes_sieve(LIMIT)
print time()-s
나는이 질문에 느리게 응답하지만 재미있는 운동처럼 보입니다. 나는 속일 수있는 numpy를 사용하고 있으며이 방법이 가장 빠르지 만 명확해야합니다. 인덱스 만 참조하는 부울 배열을 체로 만들고 모든 True 값의 인덱스에서 소수를 도출합니다. 모듈로가 필요하지 않습니다.
import numpy as np
def ajs_primes3a(upto):
mat = np.ones((upto), dtype=bool)
mat[0] = False
mat[1] = False
mat[4::2] = False
for idx in range(3, int(upto ** 0.5)+1, 2):
mat[idx*2::idx] = False
return np.where(mat == True)[0]
다음은 파이썬의 목록 이해를 사용하여 소수를 생성하는 흥미로운 기술입니다.
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]
여기 에서 예제와 설명을 찾을 수 있습니다
내가 찾은 가장 간단한 방법은 다음과 같습니다.
primes = []
for n in range(low, high + 1):
if all(n % i for i in primes):
primes.append(n)
참고 URL : https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n
반응형
'development' 카테고리의 다른 글
| 소프트웨어 디자인과 소프트웨어 아키텍처 비교 (0) | 2020.03.02 |
|---|---|
| int 또는 Int32를 사용해야합니까 (0) | 2020.03.02 |
| LINQ로 주문 유지 (0) | 2020.03.02 |
| 오류 : 기본 클래스를 찾거나로드 할 수 없습니다. (0) | 2020.03.02 |
| github.com 사용자에게 메시지를 남기는 방법 (0) | 2020.03.02 |