Простые числа сита Python

Question

Я пытаюсь получить сумму всех простых чисел, используя сито на Python 2.7. Однако, когда я запускаю программу, я получаю только 0 каждый раз. Я понятия не имею, почему это происходит.

import math,time 

start=time.clock() 

def primesieve(limit): 
    final=0 
    a=[True]*limit 
    a[0]=a[1]=False 
    for i,isprime in enumerate(a): 
    if isprime: 
     for n in xrange(i,limit,i): 
     a[n]=False 
    for i in xrange(limit): 
    if a[i]: 
     final=final+i 
    return final 

print primesieve(2000000) 

elapsed=time.clock()-start 

print elapsed 

Answer 1

for n in xrange(i,limit,i): 
    a[n]=False 

Оно должно быть:

for n in xrange(2*i,limit,i): 
    a[n]=False 

Или, более эффективно:

for n in xrange(i*i,limit, 2*i): #assuming you already cleared even numbers 
    a[n]=False 

Потому что в противном случае вы в конечном итоге установка i как не-премьер, когда он на самом деле является премьер. (Сито следует отметить все кратные i как не-простые числа, за исключением самого i!)

---

Обратите внимание, что вы перебираете все числа, до limit, но вы можете безопасно остановить после достижения sqrt(limit):

import itertools as it 

def primesieve(limit): 
    a = [True] * limit 
    a[0] = a[1] = False 
    sqrt_limit = int(limit**0.5) + 1 
    predicate = lambda x: x[0] <= sqrt_limit 
    for i, isprime in it.takewhile(predicate, enumerate(a)): 
     if isprime: 
      for n in xrange(i*i, limit, i): 
       a[n] = False 
    return sum(i for i,n in enumerate(a) if n) 

takewhile функция прекращает итерацию сразу после достижения квадратного корня из limit. i*i не даст ошибок, поскольку он всегда будет меньше limit.

На моей машине это примерно в два раза быстрее, чем итерация по всем номерам.

Answer 2

Посмотрите на эту тему: Fastest way to list all primes below N быстрого решета ниже 8 * 10^8 является rwh_prime1 кодируется @Robert Уильям Хэнкс

'''Robert William Hanks 2010''' 
def primes1(n): 
    """ 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]]