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