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]
Saturday, May 09, 2009
JavaOne Talk: Python Prime Sieve
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment