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?

2 comments

Phil Huffman (author) 13 years, 4 months ago  # | flag

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 13 years, 3 months ago  # | flag

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