Help with computing nth prime number

[abhijat]

Hi guys,

I'm new to the forum and to progamming. I've started following a set of online video lectures as an introduction to programming using python. One of the problem they asked to solve is to create a simple program that computes and prints the 1000th prime number.

I got the following so far:

count = 1 #counts the prime number. With already there, the number "2"
num = 2 

prime = [2] #creates a list with "2" already in there
while (count <1000): 
	if num%2 !=0: 
		count = count+1 #increase by one every time there is a prime number
		prime.append(num) #add the prime number to the list
		
	num = num + 1
print prime [:10] #prints the 10th prime number

But instead of showing the the 1000th (or 10th) prime number, it seems to be only displaying odd numbers (and 2).

I'm guessing I've done something wrong here:

if num%2 !=0:

We have only been introduced to basics such as loops, variables and boolean operators so I want to keep it simple.

I would appreciate any help. With thanks in advance,

[TrustyTony]

you must test for each number which is prime. You can stop checking when the prime**2 is bigger than maximum value of candidates. To be sure to find the 1000 use for example list of 100 000 truth values all True in beginning. Then take each prime*n (every nth) by putting truth value False in those indexes.
When you have reached the point 100000**0.5 you can stop process an count 1000 True values from beginning of list and return index of that. This is called sieve of Eratosthenes. You can find optimized code for that in this forums code snippets after you have made your code.

[griswolf]

As you might guess, this is a much discussed topic. Here's a bunch of prime generators: http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python

[griswolf]

Quite aside from speed, I'm annoyed by the fact that we seem to be calling these prime sieves "generators". I decided to try to write an open-ended actual generator:

import math
def anotherPrime():
  primeslist = []
  if not 2 in primeslist:
    primeslist.append(2)
    yield 2
  if not 3 in primeslist:
    primeslist.append(3)
    yield 3
  next = primeslist[-1] + 2
  while True:
    couldbeprime = True
    for p in primeslist:
      if 0 == next % p:
        couldbeprime = False
        break
      if p > math.sqrt(next)+1:
        break
    if couldbeprime:
      primeslist.append(next)
      yield next
    next += 2

def nthPrime(n):
  gen = anotherPrime()
  for i in range(n):
    gen.next()
  print "%d: %d"%(n,gen.next())


if "__main__" == __name__:
  import datetime as dt
  for nth in range(1000,10010,1000):
    start = dt.datetime.now()
    nthPrime(nth)
    end = dt.datetime.now()
    print "For %d, %s"%(nth,end-start)

I know I should use timeit for this, but I never have; and I know how to do it this way (ugly as it is).

Obviously, this is not a fast implementation, though if you twisted it around a little bit to make it a class that kept a cache of known primes, it would be "fast enough on small enough numbers".

[TrustyTony]

griswolf: sieve not generator, make a real generator for primes

Here is my optimized version of fastest pure python (not using numpy) sieve together with original code (definitely not basic sieve).

In real use this should be optimized with sieve extension instead of generation from beginning when sieve finishes:

def rwh_primes1(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * (n//2)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]

def primes(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    # recursive formula for length by amount1 and amount2 tjv
    """ Returns  a list of primes < n """
    sieve = [True] * (n//2)
    amount1 = n-10
    amount2 = 6

    for i in range(3,int(n**0.5)+1,2):
        if sieve[i//2]:
             ## can you make recursive formula for whole reciprocal?
            sieve[i*i//2::i] = [False] * (amount1//amount2+1)
        amount1-=4*i+4
        amount2+=4

    return [2] + [2*i+1 for i in xrange(1,n//2) if sieve[i]]

def primes_gen(nth=1,number_of_prime=False):
    """Generate primes starting from nth prime,
    give tuple of prime number and prime itself if parameter
    number_of_prime is True"""
    sieve_max=100000
    prime_no=nth
    while True:
        for prime in primes(sieve_max)[nth-1:]:
            yield (prime_no,prime) if number_of_prime else prime
            prime_no+=1
        sieve_max*=2
        n=prime_no

for prime_no, prime in primes_gen(995, number_of_prime = True):
    if prime_no>1005: break
    else: print "%4i: %i" % (prime_no, prime)

print 'Check: %ith prime is %i' % (1000,primes(10000)[1000-1])

for prime in primes_gen(1005):
    if prime<8100:
        print prime,
    else:
        break

""" Output:
 995: 7877
 996: 7879
 997: 7883
 998: 7901
 999: 7907
1000: 7919
1001: 7927
1002: 7933
1003: 7937
1004: 7949
1005: 7951
Check: 1000th prime is 7919
7951 7963 7993 8009 8011 8017 8039 8053 8059 8069 8081 8087 8089 8093
"""

[TrustyTony]

Recursive formula in my comment should properly be called recurrence formula and I would be grateful if somebody knows to deal with the division fast enough to eliminate that also (it is however done only when entering inside the if). If some numpy expert could see if the recurrence formula can speed the calculation in those versions, I would be interested to see the implementation.

Also if you could time in your machine the performance of my primes with recurrence, I would be grateful.

BTW if you use psyco module, it speeds things dramatically and also simplest solutions take more benefit from it.

griswolf: 2 is your 0th prime

>>> nthPrime(1)
1: 3

BUG IN MY CODE LINE 38:

Old variable name n, should be nth

[ultimatebuster]

generating prime number cannot be very simple, what you're doing is generating odd numbers

The % operator is the modulos operator. The mod operator calculates the remainder of a division operation.

For example:

5 / 2 = 2.5

5 % 2 = 1

because 5 divide by 2 has an remainder of one (from grade 1 math, please tell me you know this ;))

Prime numbers are much more complicated. They cannot be with only a %2 operation. Wikipedia has a list of different algorithm you can implement.

[griswolf]

generating prime number cannot be very simple, what you're doing is generating odd numbers...

Indeed, except for 2, all prime numbers are odd. Look more closely (or run the code) and you will see that the work of eliminating other composites is being done. In my code, it is in the loop through previously found primes at line 13. Not sure about the code posted by tonyjv. Some of thet code is from a discussion of primes at stackoverflow.com, as he mentioned in his comments.

[vegaseat]

You may also want to look at Henri Bumsfeld's Prime Number Function Improvements (Python) at:
http://www.daniweb.com/code/snippet216871.html

[TrustyTony]

Thanks for link, vegaseat.

I added the versions I posted stackoverflow, and my optimization of that. Results are in my computer:

timing results for r=9000
get_primes1 took 2151.789 ms
get_primes2 took 384.671 ms
get_primes3 took 115.143 ms
get_primes4 took 85.908 ms
get_primes5 took 20.468 ms
get_primes7 took 2.279 ms
rwh_primes1 took 1.297 ms
primes took 1.271 ms

Little confusing that primes6 is missing.

[vegaseat]

I took one of Henri's more conventional prime list functions and modified it to return when the nth prime is reached. Actually, you don't even have to create the list.

You can waste a lot of time improving sieve based prime number functions, but then somebody comes along and uses module numpy, increasing the speed ten times over anything else.

[TrustyTony]

Yes, there seems to be some sieves specially adapted for nth prime finding with generator functions and impoving the sieve is more like game and learning experience of Python techniques, when simple C implementation can be much faster as long as you keem under 2e9 values at least, then better to store flags in bits for memory reasons and have print_from_nth_prime_to style function to do the [2n+1... generation from that, not for all sieve without purpose.

I only used the standard sieve as it took less effort.

http://code.activestate.com/recipes/117119-sieve-of-eratosthenes/
http://books.google.com/books?id=Q0s6Vgb98CQC&lpg=PT703&dq=python%20cookbook%20sieve&pg=PT703#v=onepage&q&f=false

[TrustyTony]

Quite aside from speed, I'm annoyed by the fact that we seem to be calling these prime sieves "generators". I decided to try to write an open-ended actual generator:

import math

I know I should use timeit for this, but I never have; and I know how to do it this way (ugly as it is).

Obviously, this is not a fast implementation, though if you twisted it around a little bit to make it a class that kept a cache of known primes, it would be "fast enough on small enough numbers".

I found suggestion for real generator sieve in python-list:

def sieve():
    innersieve = sieve()
    prevsquare = 1
    table = {}
    i = 2
    while True:
        if (table.has_key(i)):
            prime = table[i]
            del(table[i])
            nextone = i+prime
            while nextone in table:
                nextone = nextone + prime
            table[nextone] = prime
        else:
            yield i
            if i > prevsquare:
                j = innersieve.next()
                prevsquare = j * j
                table[prevsquare] = j
        i = i + 1 

Timing is not so special, but I do not know if it would be better or worse than yours. As vegaseat said it is stupid to return as list the primes from this kind of solution.