Uses an array to store the values, expands the size of the prime list on the fly, you can make a guess at how many you will need. I am finding it useful for the problems at http://projecteuler.net Any thoughts for improvement appreciated (I am going to try and neaten it up with a few list comprehensions and possibly speed up the initial array creation)
Python, 45 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | class PrimeList:
def __init__(self, initial=0):
self.primelist = [2]
self.primelookup = [0,0,1,1]
self.max_prime = 2
self.initialise_list(initial)
def initialise_list(self,upto):
"Good old Sieve of Eratosthenes"
if upto <= 3:
pass
self.primelookup.extend([0,1] * ((upto-3)//2))
if upto % 2 == 0:
self.primelookup.extend([0])
for i in range(3, upto + 1 , 2):
if self.primelookup[i]:
self.primelist.append(i)
self.max_prime = i
j = i + i
while j <= upto:
self.primelookup[j] = 0
j += i
def __contains__(self,number):
if number < 2:
return False
if number > self.max_prime - 1:
#print "Asking for what I dont have!"
return self._isprime(number)
return self.primelookup[number]
def _isprime(self, number):
for prime in self.primelist:
if prime > number ** .5:
break
if number % prime == 0:
return False
if number < self.max_prime ** 2:
return True
else:
#Brute forcing
for i in range(self.max_prime,number ** .5 + 1, 2):
if number % i == 0:
return False
return True
|
Tags: algorithms
alternate implementation. I posted an arguably simpler implementation to comp.lang.python:
http://mail.python.org/pipermail/python-list/2007-August/452949.html
You resisted saying "arguably better" and it probably is, though perhaps I should say was as you reminded me to update it to the one I use now.
You resisted saying "arguably better" and it probably is, though perhaps I should say was as you reminded me to update it to the one I use now.
Speeding up the creation. Hello, although I do not know the problem you refer to, here are a couple of suggestions to speed up the initial creation (function initialize_list):
Use xrange instead of range (consumes less ressources)
Suppress only odd multiples of the prime. The even multiples are already taken out of the list when created. So for instance for i=3, I would suppress 9, 15, 21... instead of 6, 9, 12, 15...
The logic mentionned in point 2 can be pusehd a little bit further: instead of creating an array of repeated [0,1], create an array of half the length, all [1]. Position i in that array would represent number 2 * i + 1.
Hope this helps...
Marc