I was creating a Carmichael triplets generator and needed a function to tell me if a number was prime. It wasn't immediately clear what the largest prime for checking would be so I decided to look into creating an extensible prime generator - If given a number to check for prime-ness that was outside its range, it would attempt to extend its range.
I stopped modifying the class as soon as it was working as the Carmichael generator task then ran in acceptable time.
class Isprime(): ''' Extensible sieve of Erastosthenes >>> isprime.check(11) True >>> isprime.multiples {2, 4, 6, 8, 9, 10} >>> isprime.primes [2, 3, 5, 7, 11] >>> isprime(13) True >>> isprime.multiples {2, 4, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22} >>> isprime.primes [2, 3, 5, 7, 11, 13, 17, 19] >>> isprime.nmax 22 >>> ''' multiples = {2} primes = [2] nmax = 2 def __init__(self, nmax): if nmax > self.nmax: self.check(nmax) def check(self, n): if type(n) == float: if not n.is_integer(): return False n = int(n) multiples = self.multiples if n <= self.nmax: return n not in multiples else: # Extend the sieve primes, nmax = self.primes, self.nmax newmax = max(nmax*2, n) for p in primes: multiples.update(range(p*((nmax + p + 1) // p), newmax+1, p)) for i in range(nmax+1, newmax+1): if i not in multiples: primes.append(i) multiples.update(range(i*2, newmax+1, i)) self.nmax = newmax return n not in multiples __call__ = check
Now I wouldn't be surprised if some of the loop indices are not optimum and are maybe recomputing a few values that don't need to be, and this code is only efficient enough for my purposes; (a couple of Rosetta Code entries in other languages state that they are based on the Python but make changes so that is an indication).
Some problems...
ReplyDeleteIn [72]: Isprime(2).check(41)
Out[72]: True
In [73]: isprime = Isprime(2)
In [74]: isprime.
isprime.__call__ isprime.__class__ isprime.__doc__ isprime.__init__ isprime.__module__ isprime.check isprime.multiples isprime.nmax isprime.primes
In [74]: isprime.multiples
Out[74]:
set([2,
4,
6,
8,
9,
10,
12,
14,
15,
16,
18,
20,
21,
22,
24,
25,
26,
27,
28,
30,
32,
33,
34,
35,
36,
38,
39,
40])
In [75]: isprime.nmax
Out[75]: 2
In [76]: isprime.primes
Out[76]: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
In [77]: isprime(43)
Out[77]: True
In [78]: isprime.nmax
Out[78]: 43
In [79]: isprime.primes
Out[79]: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 3, 43]
In [80]: isprime.multiples
Out[80]:
set([2,
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])
In [81]: isprime(41)
Out[81]: False
In [82]: isprime(29)
Out[82]: False
In [83]: isprime(23)
Out[83]: False
In [84]: isprime.nmax
Out[84]: 43