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

4 comments

Steven Bethard 14 years, 3 months ago  # | flag

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) 14 years, 3 months ago  # | flag

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) 14 years, 3 months ago  # | flag

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 14 years, 3 months ago  # | flag

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)
Python recipes (4591)
thattommyhall ;'s recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks