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)