ps1a.py

##################################################################################################################################
# Note, that the first prime in the set of primes is 2. Therefore, when we start checking the next prime candidate by dividing   #
# it by all the previous primes, the first prime we divide the cadidate by is 2 and, thus, first, we check if the number is even #
# or odd. If it's even, then the candidate is rejected and we start checking the next candidate.                                 #
##################################################################################################################################

import math

Primes = [2] #stores all computed primes

NumberOfPrimes = len(Primes) #holds the number of primes in the list Primes

while NumberOfPrimes < 10000:

    n = Primes[NumberOfPrimes - 1] + 1 #next prime candidate

    i = 0

    while i < len(Primes) and Primes[i] <= int(math.sqrt(n)): #divide the cadidate by all the previous primes up to the square root of the candidate

        #print "Prime candidate",n,"i is",i

        if n % Primes[i] == 0:

            n = n + 1          #if there's a remainder choose the next candidate

            i = 0              #reset counter to start checking from the beginning of the set of primes

        else:

            i = i + 1 #continue checking primality of the candidate with next prime in the set of primes

    Primes.append(n) #the candidate couldn't be divided without remainder by any of the previous primes, the candidate is prime, append it to the list

    NumberOfPrimes = len(Primes) #update the number of primes

print "The 1000th prime is", Primes[999]
#print "The 2000th prime is", Primes[1999]
#print "The 3000th prime is", Primes[2999]
#print "The 4000th prime is", Primes[3999]
#print "The 5000th prime is", Primes[4999]
#print Primes