Primes

[Frenzic]

Hi, I'm stumped at this problem set and was wondering if anyone could guide me in the right direction or give me some hints on where to begin. I'm not looking for a full answer.

Q: Write a program that computes and prints the 1000th prime number.

Any help is appreciated.

Kind regards,
Frenzic

[snippsat]

Hint.

for i in range(2, 1000):
	print i

>>> 2 % 2 == 0
True
>>> 3 % 2 == 0
False
>>> 4 % 2 == 0
True
>>> 5 % 2 == 0
False
>>>

[lllllIllIlllI]

There are a great many prime number generators in the code snippet sections :)

http://www.daniweb.com/code/forum114.html

Otherwise, i would look at techniques to find primes. Then come back with some code if you have any issues.

Here is a great idea http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

[vegaseat]

As a hint, here is a slow but simple prime number algorithm ...

# slow and simple algorithm to find prime numbers
# prime numbers are only divisible by unity and themselves
# (1 is not considered a prime number)

limit = 20
# 2 is the first prime number
plist = [2]
for n in range(3, limit):
  for x in range(2, n):
    if n % x == 0:
      break
  else:
    # this else has to line up with the inner for, not the if
    # implies that the loop fell through without finding a factor
    #print n, 'is a prime number'  # test
    plist.append(n)

print "prime list  =", plist
print "list length =", len(plist)
print "third prime =", plist[2]
print "last prime  =", plist[-1]

"""my result -->
prime list  = [2, 3, 5, 7, 11, 13, 17, 19]
list length = 8
third prime = 5
last prime  = 19
"""

You could set the limit higher to get to the 1000th prime number in the list. It will take time. There are clever ways to improve the speed, but I leave that as an exercise. Also check if there is a relationship between the minimum limit and the size of the prime number list.

[pysup]

Try this : (modified vegaseat's code)

It wil print the 1000th prime number

prime_no_cnt = 2        # store first 3 prime numbers and start with 5 (because of n/2)
plist = [2,3]

n = 5
while 1 :
        flag = 1
        for x in range(2, n/2):
                if n % x == 0:
                        flag=0
                        break

        if flag != 0 :
                plist.append(n)
                prime_no_cnt = prime_no_cnt + 1
                #print n
        if prime_no_cnt == 1000 :
                print n
                break
        else :
                n = n + 1