Sieve of Eratosthenes-primes

SyntaxHighlighter.config.bloggerMode=true; SyntaxHighlighter.config.clipboardSwf=’http://alexgorbatchev.com/pub/sh/current/scripts/clipboard.swf’; SyntaxHighlighter.all(); My python diaries… hello all, Recently I was experimenting with sieve method for finding primes in python… This code is really fast and memory saving than the ones commonly avaliable have a look…
It produced 100000000 primes on my 2.4Ghz i7 machine in just few seconds…



# Aritra Kundu
# arsenous.blogspot.com
'''
create prime numbers list using sieve method
'''
import numpy as np
import time as ti

def primes_up_to(n):
rootn=int(np.sqrt(n))
sieve=[True]*(n+1) #create a n+1 arrray
#set 0,1, false +ve
sieve[0]=sieve[1]=False

for i in xrange(2,rootn+1):
if sieve[i]:
no_of_multiples=n/i-i
sieve[i*i:n+1:i]=[False]*(no_of_multiples+1)

return [i for i in xrange(n+1) if sieve[i]]

#a second commonly avaliable method..the above is almost 30% faster as it uses binary and memory saving...
def primes_up_to2(n):
rootn=int(np.sqrt(n))
sieve=xrange(n+1) #create a n+1 arrray
#set 0,1, false +ve
sieve[0]=sieve[1]=0

for i in xrange(2,rootn+1):
if sieve[i] !=0:
no_of_multiples=n/i-i
sieve[i*i:n+1:i]=[0]*(no_of_multiples+1)

sieve=[x for x in sieve if x !=0]
#print sieve
return sieve

def count_primes_up_to(n):
return len(primes_up_to(n))

N=1000000

def save_primes():
t=ti.time()
sieve_file=open('sieve_primes_%s'%N,'w')
p=primes_up_to(N)
print len(p)
sieve_file.writelines("%s\n"%len(p))
sieve_file.writelines(["%s\n" %item for item in p])
t=ti.time()-t
print 'TF modified',t
sieve_file.close()

def is_prime(n):
return n in primes_up_to(n)