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
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.
No comments:
Post a Comment