CODEWITHSUNDEEP
pythonsieve-algorithm
user2604347
user2604347

Reputation: 11

Python sieve prime numbers

I am trying to get the sum of all prime numbers using a sieve on Python 2.7. However when I run the program I only wind up with 0 everytime. I have no idea why this is happening.

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

Upvotes: 1

Views: 1047

Answers (2)

ABri
ABri

Reputation: 618

Have a look at this related topic: Fastest way to list all primes below N Fastest sieve below 8 * 10^8 is rwh_prime1 coded by @Robert William Hanks 

'''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]]

Upvotes: 2

Bakuriu
Bakuriu

Reputation: 101989

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

It should be:

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

Or, more efficiently:

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

Because otherwise you end up setting i as non-prime, when it actually is a prime. (The sieve should mark all multiples of i as non-primes, except i itself!)

Note that you are iterating over all the numbers, up to limit, but you can safely stopped after reaching 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)

The takewhile function will stop the iteration right after reaching the square root of limit. The i*i wont give errors since it will always be smaller than limit.

On my machine it is about twice as fast as iterating over all the numbers.

Upvotes: 2

Related Questions