에라토스테네스의 체-소수 찾기 파이썬
명확히하기 위해 이것은 숙제 문제가 아닙니다. :)
내가 만들고있는 수학 응용 프로그램의 소수를 찾고 싶었고 Sieve of Eratosthenes 접근 방식을 발견했습니다.
나는 그것을 파이썬으로 구현했다. 그러나 그것은 매우 느립니다. 예를 들어, 2 백만 미만의 모든 소수를 찾으려면. 20 분 이상 걸립니다. (이 시점에서 중지했습니다). 속도를 높이려면 어떻게해야합니까?
def primes_sieve(limit):
limitn = limit+1
primes = range(2, limitn)
for i in primes:
factors = range(i, limitn, i)
for f in factors[1:]:
if f in primes:
primes.remove(f)
return primes
print primes_sieve(2000)
업데이트 : 나는이 코드에 대한 프로파일 링을 끝내고 목록에서 요소를 제거하는 데 많은 시간이 소요되었음을 발견했습니다. 요소를 찾기 위해 전체 목록 (최악의 경우)을 탐색 한 다음 제거하고 목록을 다시 조정해야한다는 점을 고려하면 이해할 수 있습니다 (일부 사본이 계속 될 수 있습니까?). 어쨌든, 나는 사전 목록을 뽑았다. 내 새로운 구현-
def primes_sieve1(limit):
limitn = limit+1
primes = dict()
for i in range(2, limitn): primes[i] = True
for i in primes:
factors = range(i,limitn, i)
for f in factors[1:]:
primes[f] = False
return [i for i in primes if primes[i]==True]
print primes_sieve1(2000000)
올바른 알고리즘을 구현하고 있지 않습니다.
첫 번째 예에서는 primes_sieve알고리즘에서와 같이 스트라이크 / 설정 해제 할 소수 플래그 목록을 유지하지 않고 대신 정수 목록의 크기를 지속적으로 조정하므로 매우 비용이 많이 듭니다. 목록에서 항목을 제거하려면 모든 후속 항목을 이동해야합니다. 하나씩 아래로.
두 번째 예에서는 올바른 방향의 한 단계 인 소수성 플래그 사전 을 primes_sieve1유지 하지만 정의되지 않은 순서로 사전을 반복하고 알고리즘에서와 같이 소수의 요소 만 제거하는 대신 요소의 요소를 중복 제거합니다. ). 키를 정렬하고 프라임이 아닌 부분을 건너 뛰어이 문제를 해결할 수 있지만 (이미 한 단계 더 빠름) 목록을 직접 사용하는 것이 훨씬 더 효율적입니다.
올바른 알고리즘 (사전 대신 목록 포함)은 다음과 같습니다.
def primes_sieve2(limit):
a = [True] * limit # Initialize the primality list
a[0] = a[1] = False
for (i, isprime) in enumerate(a):
if isprime:
yield i
for n in range(i*i, limit, i): # Mark factors non-prime
a[n] = False
(여기에는 i*i이중 대신 프라임 사각형 ( ) 에서 프라임이 아닌 마킹을 시작하는 알고리즘 최적화도 포함됩니다 .)
def eratosthenes(n):
multiples = []
for i in range(2, n+1):
if i not in multiples:
print (i)
for j in range(i*i, n+1, i):
multiples.append(j)
eratosthenes(100)
배열 (목록)의 시작 부분에서 제거하려면 모든 항목을 아래로 이동해야합니다. 즉, 이러한 방식으로 맨 앞에서 시작하여 목록에서 모든 요소를 제거하는 것은 O (n ^ 2) 작업입니다.
세트를 사용하면이 작업을 훨씬 더 효율적으로 수행 할 수 있습니다.
def primes_sieve(limit):
limitn = limit+1
not_prime = set()
primes = []
for i in range(2, limitn):
if i in not_prime:
continue
for f in range(i*2, limitn, i):
not_prime.add(f)
primes.append(i)
return primes
print primes_sieve(1000000)
... 또는 목록을 재정렬하지 않아도됩니다.
def primes_sieve(limit):
limitn = limit+1
not_prime = [False] * limitn
primes = []
for i in range(2, limitn):
if not_prime[i]:
continue
for f in xrange(i*2, limitn, i):
not_prime[f] = True
primes.append(i)
return primes
훨씬 더 빨리:
import time
def get_primes(n):
m = n+1
#numbers = [True for i in range(m)]
numbers = [True] * m #EDIT: faster
for i in range(2, int(n**0.5 + 1)):
if numbers[i]:
for j in range(i*i, m, i):
numbers[j] = False
primes = []
for i in range(2, m):
if numbers[i]:
primes.append(i)
return primes
start = time.time()
primes = get_primes(10000)
print(time.time() - start)
print(get_primes(100))
나는 이것이 어떻게 소수를 빠르게 생성하는지에 대한 질문에 실제로 답하는 것이 아니라는 것을 알고 있지만, 아마도이 대안이 흥미로울 것입니다. 파이썬이 생성기를 통해 게으른 평가를 제공하기 때문에 에라토스테네스의 체는 명시된대로 정확하게 구현 될 수 있습니다.
def intsfrom(n):
while True:
yield n
n += 1
def sieve(ilist):
p = next(ilist)
yield p
for q in sieve(n for n in ilist if n%p != 0):
yield q
try:
for p in sieve(intsfrom(2)):
print p,
print ''
except RuntimeError as e:
print e
try 블록은 알고리즘이 스택을 날릴 때까지 실행되고 try 블록이 없으면 backtrace가 표시되어 화면에서 보려는 실제 출력을 푸시하기 때문에 존재합니다.
(위의 의견에서 Glenn Maynard 및 MrHIDEn 포함) 많은 애호가의 기여를 결합하여 파이썬 2에서 다음 코드를 생각해 냈습니다.
def simpleSieve(sieveSize):
#creating Sieve.
sieve = [True] * (sieveSize+1)
# 0 and 1 are not considered prime.
sieve[0] = False
sieve[1] = False
for i in xrange(2,int(math.sqrt(sieveSize))+1):
if sieve[i] == False:
continue
for pointer in xrange(i**2, sieveSize+1, i):
sieve[pointer] = False
# Sieve is left with prime numbers == True
primes = []
for i in xrange(sieveSize+1):
if sieve[i] == True:
primes.append(i)
return primes
sieveSize = input()
primes = simpleSieve(sieveSize)
내 컴퓨터에서 10의 거듭 제곱으로 다른 입력을 계산하는 데 걸리는 시간은 다음과 같습니다.
- 3 : 0.3ms
- 4 : 2.4ms
- 5 : 23ms
- 6 : 0.26 초
- 7 : 3.1 초
- 8:33 초
간단한 속도 해킹 : "primes"변수를 정의 할 때 모든 짝수를 자동으로 건너 뛰려면 단계를 2로 설정하고 시작 지점을 1로 설정합니다.
그런 다음 프라임에서 i 대신 프라임 [: round (len (primes) ** 0.5)]에서 i를 사용하여 추가로 최적화 할 수 있습니다. 그러면 성능이 크게 향상됩니다. 또한 속도를 더 높이기 위해 5로 끝나는 숫자를 제거 할 수 있습니다.
내 구현 :
import math
n = 100
marked = {}
for i in range(2, int(math.sqrt(n))):
if not marked.get(i):
for x in range(i * i, n, i):
marked[x] = True
for i in range(2, n):
if not marked.get(i):
print i
여기에 메모리 효율이 더 높은 버전이 있습니다 (그리고 시험 분할이 아닌 적절한 체). 기본적으로 모든 숫자의 배열을 유지하고 소수가 아닌 숫자를 지우는 대신 발견 된 각 소수에 대해 하나씩 카운터 배열을 유지하고 추정 소수보다 앞서 도약합니다. 이렇게하면 가장 높은 소수까지가 아니라 소수의 수에 비례하는 저장소를 사용합니다.
import itertools
def primes():
class counter:
def __init__ (this, n): this.n, this.current, this.isVirgin = n, n*n, True
# isVirgin means it's never been incremented
def advancePast (this, n): # return true if the counter advanced
if this.current > n:
if this.isVirgin: raise StopIteration # if this is virgin, then so will be all the subsequent counters. Don't need to iterate further.
return False
this.current += this.n # pre: this.current == n; post: this.current > n.
this.isVirgin = False # when it's gone, it's gone
return True
yield 1
multiples = []
for n in itertools.count(2):
isPrime = True
for p in (m.advancePast(n) for m in multiples):
if p: isPrime = False
if isPrime:
yield n
multiples.append (counter (n))
당신은 그주의거야 primes()당신이 목록에서 결과를 유지할 수 있습니다 또는 당신이 직접 사용할 수 있도록, 발전기입니다. 다음은 첫 번째 n소수입니다.
import itertools
for k in itertools.islice (primes(), n):
print (k)
그리고 완성도를 위해 다음은 성능을 측정하는 타이머입니다.
import time
def timer ():
t, k = time.process_time(), 10
for p in primes():
if p>k:
print (time.process_time()-t, " to ", p, "\n")
k *= 10
if k>100000: return
궁금한 점이있을 경우를 대비 primes()하여 간단한 반복자 ( __iter__및 사용 __next__)로 작성했으며 거의 동일한 속도로 실행되었습니다. 저도 놀랐습니다!
속도 때문에 NumPy를 선호합니다.
import numpy as np
# Find all prime numbers using Sieve of Eratosthenes
def get_primes1(n):
m = int(np.sqrt(n))
is_prime = np.ones(n, dtype=bool)
is_prime[:2] = False # 0 and 1 are not primes
for i in range(2, m):
if is_prime[i] == False:
continue
is_prime[i*i::i] = False
return np.nonzero(is_prime)[0]
# Find all prime numbers using brute-force.
def isprime(n):
''' Check if integer n is a prime '''
n = abs(int(n)) # n is a positive integer
if n < 2: # 0 and 1 are not primes
return False
if n == 2: # 2 is the only even prime number
return True
if not n & 1: # all other even numbers are not primes
return False
# Range starts with 3 and only needs to go up the square root
# of n for all odd numbers
for x in range(3, int(n**0.5)+1, 2):
if n % x == 0:
return False
return True
# To apply a function to a numpy array, one have to vectorize the function
def get_primes2(n):
vectorized_isprime = np.vectorize(isprime)
a = np.arange(n)
return a[vectorized_isprime(a)]
출력을 확인하십시오.
n = 100
print(get_primes1(n))
print(get_primes2(n))
[ 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]
[ 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]
Jupyter Notebook에서 Sieve of Eratosthenes와 brute-force의 속도를 비교합니다. 에라토스테네스의 체는 백만 요소에 대해 무차별 대입보다 539 배 더 빠릅니다.
%timeit get_primes1(1000000)
%timeit get_primes2(1000000)
4.79 ms ± 90.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
2.58 s ± 31.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
루프의 종료 조건으로 빈 목록을 간단히 사용할 수 있어야한다고 생각하고 다음과 같이 생각해 냈습니다.
limit = 100
ints = list(range(2, limit)) # Will end up empty
while len(ints) > 0:
prime = ints[0]
print prime
ints.remove(prime)
i = 2
multiple = prime * i
while multiple <= limit:
if multiple in ints:
ints.remove(multiple)
i += 1
multiple = prime * i
import math
def sieve(n):
primes = [True]*n
primes[0] = False
primes[1] = False
for i in range(2,int(math.sqrt(n))+1):
j = i*i
while j < n:
primes[j] = False
j = j+i
return [x for x in range(n) if primes[x] == True]
내 가장 빠른 구현 :
isprime = [True]*N
isprime[0] = isprime[1] = False
for i in range(4, N, 2):
isprime[i] = False
for i in range(3, N, 2):
if isprime[i]:
for j in range(i*i, N, 2*i):
isprime[j] = False
나는 이것이 eratosthenes 방법으로 소수를 찾는 가장 짧은 코드라고 생각합니다.
def prime(r):
n = range(2,r)
while len(n)>0:
yield n[0]
n = [x for x in n if x not in range(n[0],r,n[0])]
print(list(prime(r)))
참고 URL : https://stackoverflow.com/questions/3939660/sieve-of-eratosthenes-finding-primes-python
'developer tip' 카테고리의 다른 글
| .net MVC RadioButtonFor ()를 사용할 때 하나만 선택할 수 있도록 그룹화하는 방법은 무엇입니까? (0) | 2020.11.24 |
|---|---|
| MySQL CASE는 어떻게 작동합니까? (0) | 2020.11.24 |
| numpy.matrix 또는 배열을 scipy 희소 행렬로 변환하는 방법 (0) | 2020.11.24 |
| PDO PHP에서 쿼리 오류를 보는 방법 (0) | 2020.11.24 |
| 두 목록을 C #의 사전에 매핑 (0) | 2020.11.23 |