Welcome, guest | Sign In | My Account | Store | Cart

Finds the nth prime without using a sieve algorithm.

Python, 85 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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85``` ```#!/usr/bin/python """ nth prime """ import cPickle, math, sys, os primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] fn = 'myPrimes' interval = 123456 def fmt_n(n): """ formats an integer input: integer return: string """ nstr = '%d' % (n) nlist = list(nstr) for pos in range(len(nstr) - 3, 0, -3): nlist.insert(pos, ',') return ''.join(nlist) def isprime(n): """ tells if n is prime input: number return boolean """ global primes limit = int(math.sqrt(n)) for prime in primes: if prime > limit: return True if n % prime == 0: return False raise ValueError, "Not enough primes" def ith_prime(i): """ gets prime(i) input: number return: number """ global primes, interval while i >= len(primes): a = ((primes[-1] + 2) // 6) * 6 - 1 b = a + interval c = a + 2 d = b + 2 try: primes.extend(filter(isprime, xrange(a, b, 6))) primes.extend(filter(isprime, xrange(c, d, 6))) primes = sorted(list(set(primes))) mpp = open(fn, 'w') cPickle.dump(primes, mpp, protocol = -1) mpp.close() print 'Prime[%s] = %s' % (fmt_n(len(primes)), fmt_n(primes[-1])) except ValueError: interval = interval // 2 return primes[i] def do_input(s): try: i = int(s) except ValueError: i = len(primes) + 1 print 'Prime[%s] = %s.' % (fmt_n(i), fmt_n(ith_prime(i))) if __name__ == '__main__': try: mpp = open(fn, 'rb') primes = cPickle.load(mpp) mpp.close() except IOError, e: print '* ERROR * Could not open %s for load.%se = %s' % (fn, os.linesep, e) print 'Prime(%s) = %s' % (fmt_n(len(primes)), fmt_n(primes[-1])) for s in sys.argv[1:]: do_input(s) ```

I'm trying to learn Python. Any (helpful) suggestions/feedback is welcome. Thanks.

The program uses the fact that large prime numbers have the form 6*n +/- 1. To get all possible primes two sequences must be generated. Thats where one question is: would the program run faster looking at all odd numbers and avoid the primes = sorted(list(set(primes))) line?

Phil Huffman (author) 15 years, 9 months ago

I answered my own question. A similar program using a single filter that evaluates all odd numbers is slightly quicker. That sorted(list(set(primes))) line must be expensive.

anamolf flomana 15 years, 7 months ago

Primes numbers is a trigger to develop strategies to solve the problem, and learn programming. I`ve tried to avoid all unproductive numbers groups. The idea was cut all these groups before run a any function. Discard not odd, not divisible by 3, and succesfuly not divisible by n+2. Other problem encountered was the numbers of interactions that is necessary to verify big numbers or list numbers. The example is a very simple rutine to verify primes, but with the idea previously mentioned: http://flomana.spaces.live.com/blog/cns!3550E4D9E2BD3A98!1195.entry

 Created by Phil Huffman on Sat, 26 Jul 2008 (MIT)