# Prime number dictionary

I attempted to write a read-only dictionary, containing primes:

#inspired by http://ceasarjames.wordpress.com/2011/07/10/the-quadratic-sieve/
class PrimeDict(dict):
def __init__(self):
super(PrimeDict,self).__setitem__(2,2)
self.previous_max = 2

def __setitem__(self, key, value):
return self.__getitem__(key) #it's a read-only dict

def __delitem__(self, key):
return self.__getitem__(key) #it's a read-only dict

def __find_primes(self,n):
if n < self.previous_max: return
sieve = range(self.previous_max,n)
for x in self.keys():
i = x * ((self.previous_max - 1)//x + 1)
while i < n:
sieve[i - self.previous_max] = 0
i += x
index = self.previous_max
while index <= n ** 0.5:
if sieve[index-self.previous_max]:
i = index ** 2
while i < n:
sieve[i-self.previous_max] = 0
i += index
index += 1
self.previous_max = n
for x in sieve:
if x:
super(PrimeDict,self).__setitem__(x,x)

def __getitem__(self,key):
key = int(key)
if key>= self.previous_max:
self.__find_primes((key+1))
try:
return super(PrimeDict,self).__getitem__(key)
except:
return False


https://gist.github.com/aausch/6709819

Is there any way for me to make this class definition cleaner and/or shorter?

1. No docstrings! What does your class do and how am I supposed to use it? Also, no doctests.

2. Wouldn't it be more natural for this class to be a set of primes, rather than a dictionary mapping primes to True and other keys to False?

3. There's only one set of primes, so this is a rare opportunity to make use of the Singleton pattern. That is, each call to PrimeDict() ought to return the same object.

4. By implementing __setitem__ like this:

def __setitem__(self, key, value):
return self.__getitem__(key) #it's a read-only dict


you give callers the false impression that this operation succeeded:

>>> p = PrimeDict()
>>> p[1] = True
>>> # looks good, but:
>>> p[1]
False


Instead, you should raise an exception:

def __setitem__(self, key, value):
raise TypeError("'PrimeDict' object doesn't support item assignment")


Similarly for __delitem__:

def __delitem__(self, key):
raise TypeError("'PrimeDict' object doesn't support item deletion")

5. By deriving your class from Python's dict, you make all of the dict methods available. This means that a caller might accidentally bypass your attempt to make the dictionary read-only, by calling some other method that you haven't overridden. For example:

>>> p = PrimeDict()
>>> p.update({1: True})
>>> p[1]
True


The thing to do is not to subclass dict, but to subclass collections.abc.Mapping and have the actual dictionary be a member variable. Or, if you take my suggestion in point 2 above, subclass collections.abc.Set and have the actual set as a member variable. I'll show how to do this in my revised code in section 2 below.

6. The method __find_primes has a private name. Why do you do that? The intended use of private names in Python is to "avoid name clashes of names with names defined by subclasses" but that's obviously not necessary here. All that the private name achieves here is to make your code a bit harder to debug:

>>> p = PrimeDict()
>>> p.__find_primes(10)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: 'PrimeDict' object has no attribute '__find_primes'
>>> p._PrimeDict__find_primes(10)
>>> p
{2: 2, 3: 3, 5: 5, 7: 7}

7. You start out by adding 2 to the set of primes and then set self.previous_max = 2. But it would be simpler to start out with the empty set of primes and self.previous_max = 1. The sieve of Eratosthenes is self-starting.

i = index ** 2
while i < n:
sieve[i-self.previous_max] = 0
i += index


make use of Python's range function, and write:

for i in range(index ** 2, n, index):
sieve[i - self.previous_max] = 0

9. The code in __find_primes has to subtract self.previous_max from the array index every time it looks up something in sieve. It would be more efficient to do this subtraction once when setting up the loop bounds. For example, instead of the code that I suggested above:

for i in range(index ** 2, n, index):
sieve[i - self.previous_max] = 0


you could write:

for i in range(index ** 2 - self.previous_max, n - self.previous_max, index):
sieve[i] = 0

10. The line:

key = int(key)


can raise ValueError. Wouldn't it be better to return False if key can't be converted to an integer?

### 2. Revised code

try:
from collections.abc import Set
except ImportError:
from collections import Set # Python 3.2 or earlier

class PrimeSet(Set):
"""A PrimeSet object acts like the set of prime numbers:

>>> p = PrimeSet()
>>> 2 in p
True
>>> 4 in p
False

The object sieves for primes as needed. When iterated over, it
yields the primes found so far:

>>> 30 in p
False
>>> list(p)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

"""
# Singleton pattern: there is only one set of primes.
instance = None
def __new__(cls):
if cls.instance is None:
cls.instance = super(PrimeSet, cls).__new__(cls)
return cls.instance

def __init__(self):
super(PrimeSet, self).__init__()
self.max = 1            # Highest number sieved to so far.
self.set = set()        # Set of primes up to self.max.

def __iter__(self):
return iter(self.set)

def __len__(self):
return len(self.set)

def __contains__(self, key):
try:
key = int(key)
except ValueError:
return False
if key > self.max:
self.find_primes(key)
return key in self.set

def find_primes(self, n):
"""Sieve for primes from self.max + 1 up to and including n."""
if n <= self.max:
return
sieve = [True] * (n - self.max)
for p in self:
for i in range(p - 1 - self.max % p, len(sieve), p):
sieve[i] = False
for p, isprime in enumerate(sieve):
if isprime:
p += self.max + 1

• Point 2 is about appropriate interface for an object representing the prime numbers (should it be set-like or dictionary-like?), not about the implementation. My implementation suggestion is that you use a Python set, which of course has no values (False or otherwise), just keys. Sep 26, 2013 at 22:19