Welcome, guest | Sign In | My Account | Store | Cart

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
 ``` 1 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 ```

Steven Bethard 16 years, 1 month ago

alternate implementation. I posted an arguably simpler implementation to comp.lang.python:

http://mail.python.org/pipermail/python-list/2007-August/452949.html

thattommyhall ; (author) 16 years, 1 month ago

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.

thattommyhall ; (author) 16 years, 1 month ago

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.

Marc Vanhoomissen 16 years ago

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):

1. Use xrange instead of range (consumes less ressources)

2. 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...

3. 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

 Created by thattommyhall ; on Sun, 15 Jul 2007 (PSF)

### Required Modules

• (none specified)