Saturday, May 09, 2009

JavaOne Talk: Python Prime Sieve

See this post for an explanation on why this code is being shown and what kind of responses would be useful. See this post for the Java algorithm to compare against.

from math import log
import sys

class PyPrimes(object):
__slots__ = ['cnt','primes','size']

def __init__(self,n):
self.primes = n*[0]
self.cnt = 0
self.size = n
i = 2
max = self.calcSize()
nums = max*[True]
while i < max and self.cnt < self.size:
p = i
if nums[i]:
self.primes[self.cnt] = p
self.cnt += 1
for j in xrange(p, max/p):
nums[p*j] = False
i+= 1

def calcSize(self):
max = 2
while max/log(max) < self.size:
max = max *2 # this makes the sieve too big, but fast
return max

def last(self):
return self.primes[self.cnt - 1]

No comments: