Python과 Eratosthenes의 Sieve와 2 백만 미만의 소수의 합을 어떻게 더 빨리 효율적으로 처리 할 수 ​​있습니까?

Question

이 작업은 ~ 0.7s (2.2GHz i7 쿼드 코어)에서 작동하지만 훨씬 빠르다는 것을 알고 있습니다. 이 방법을 배우는 것이 파이썬에 관해 많은 것을 가르쳐 줄 수 있다고 생각합니다. 어떻게 속도를 올리나요? 더 많은 메모리를 효율적으로 사용하려면 어떻게해야합니까? 기록을 위해

from math import sqrt 
import time 

def sum_range(n): 
    A = [1 if i > 1 else 0 for i in xrange(n+1)] 
    for i, p in enumerate(A): 
     if A[i] and i <= int(sqrt(n)): 
      for j in xrange(i+i, n+1, i): 
       A[j] = 0 
    sum = 0 
    for i, p in enumerate(A): 
     if A[i]: 
      sum += i 
    return sum 

if __name__ == '__main__': 
    t0 = time.time() 
    sum = sum_range(1000*1000*2) 
    t1 = time.time() 
    print "The sum is {} and it took {} seconds to do this".format(sum, t1-t0) 

(멀티 프로세싱을 사용하고 여전히 에라 토 스테 네스의 체를 사용하지 않고)이 어떤 종류의 숙제 문제가되지 않습니다. 호기심을 위해서.

Answer 1

sqrt (2 * 10^6) 아래에는 223 개의 소수가 있습니다. 내가 어떻게 알았지? wolframalpha로 가서 "소수 미만의 소수점 수 (sqrt (2e6)")를 입력하십시오. 죄송합니다 이것은 Java이지만 Python에도 적용해야합니다.

long sum = 2; // treat 2 separately 
int len = (int) Math.sqrt(2000000) + 1, count = 0; 
boolean[] sieve = new boolean[len]; 
int[] primes = new int[222]; // without 2 
// do sieve only with the odd numbers and up to the root 
for (int i = 3; i < len; i += 2) { 
    if (!sieve[i]) { 
     sum += i; 
     primes[count++] = i; 
     for (int j = 3 * i; j < len; j += 2 * i) // again only odd numbers 
      sieve[j] = true; 
    } 
} 
outer: 
for (int i = len % 2 == 0 ? len + 1 : len; i < 2000000; i += 2) { 
    for (int j = 0; j < primes.length && primes[j] * primes[j] <= i; j++) 
     if (i % primes[j] == 0) 
      continue outer; 
    sum += i; 
} 

추가 개선을 위해 모든 숫자를 3으로 나눌 수도 있습니다 (세 번째 홀수는 3으로 나눌 수 있습니다).