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

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
>>>``````

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

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

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.

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``````