Skip to content

Instantly share code, notes, and snippets.

@aausch
Last active Dec 23, 2015
Embed
What would you like to do?
A read-only dictionary, which only contains prime numbers
# inspired by http://ceasarjames.wordpress.com/2011/07/10/the-quadratic-sieve/
#
# Copyright 2013, Alex Ausch
# Free to use under attribution license: http://creativecommons.org/licenses/by/2.0/ca/
try:
from collections.abc import Mapping
except ImportError:
from collections import Mapping
class PrimeSet(Mapping):
"""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]
"""
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.prime_map = {2:2}
self.previous_max = 2
def __len__(self):
return len(self.prime_map)
def __contains__(self, key):
try:
key = int(key)
except ValueError:
return False
if key > self.previous_max:
self.find_primes(key)
return key in self.prime_map
def __setitem__(self, key, value):
raise TypeError("'PrimeSet' object doesn't support item assignment")
def __delitem__(self, key):
raise TypeError("'PrimeSet' object doesn't support item removal")
def find_primes(self,n):
n = n+1 #want to include n when testing for primes
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
for index in range(self.previous_max,int(n ** 0.5)+1,1):
if sieve[index-self.previous_max]:
for i in range(index ** 2 - self.previous_max, n - self.previous_max, index):
sieve[i] = 0
self.previous_max = n
for x in sieve:
if x:
self.prime_map[x] = x
def __iter__(self):
return iter(self.prime_map)
def __getitem__(self,key):
try:
key = int(key)
except:
return False
if key>= self.previous_max:
self.find_primes(key)
try:
return self.prime_map[key]
except:
return False
@aausch
Copy link
Author

aausch commented Sep 26, 2013

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment