Finding the 1000th Prime

I mentioned the other day the homework assignment for MIT OCW Intro to CS course was to find the 1000th square root. Here is a possible solution to the problem:

primeCheck = 5
primeCount = 3
while primeCount <= 1000:
    for divisor in range(2, primeCheck//2+1):
        remainder = primeCheck % divisor
        if remainder == 0:
            break
    else:
        primeCount += 1
    primeCheck += 1
print(primeCheck - 1)

*Note - Thanks go out to Nallo who helped make my original code with clarity.

You can see we've got a few new things here. The while loop on line 3, the for loop in line 4, and a few new uses for our operators. I started explaining everything new here and it became a fairly long explanation I split into two other posts so if you want the explanation you can go there and if you just wanted to see the code you can stop here. We could also have changed 1000 to variable and inserted >>>variable = input("What prime number do you want") in the front to make this code find just about any prime.
The result is 7919 which you can also see here: List of 1000 Primes

Related posts:
Finding the 1000th Prime: Explanation
While Loops
Declaring Variables with Python
Order of Operations

Finding the 1000th Prime: Explanation

This is the explanation for the code for 1000th prime.
Here's the code again:

primeCheck = 5
primeCount = 3
while primeCount <= 1000:
    for divisor in range(2, primeCheck//2+1):
        remainder = primeCheck % divisor
        if remainder == 0:
            break
    else:
        primeCount += 1
    primeCheck += 1
print(primeCheck - 1)


I started our prime checker with 5 which is the 3rd prime. This is why the variable primeCount is 3, as it is checking for the 3rd prime. If 5 passes the test (which it does) the count will go to 4 and it will search for the fourth one. I'm using the while loop to continually repeat everything below and indented right of the while. The test for primality I have used is checking to see what the remainder is when applying the modulo operator to the possible prime and numbers 2 through half of the possible prime. It is not necessary to go further than this since all numbers above are inherently tested by testing the numbers below half.

The while loop was explained here, so I will move on to the for loop. The for loop is used when you know when you want your loop to end. We have a starting point (here it is 2) and an end (primeCheck//2+1). There are many ways to use a for loop, and the nice thing about it is you do not have to specify a counter (a variable that continually increases with each repetition of the loop, our while loop uses primeCount as the counter), it goes to the end and repeats until the end value is met.


Our end value to our for loop is primeCheck//2+1, which takes the number we are checking, 5 for instance, and does integer division on it ( // ), which gives us 2 rather than 2.5 if we used /. (Unless you are using pre-Python3 which divides based on your type and would also give two unless we changed a value to float).

Our next line is remainder = primeCheck % divisor, which performs modulo division on primeCheck by divisor. What is the modulo operator? The modulo operator is the % sign and it gives you the remainder after division of any two numbers. Here's a few examples to help you understand:

>>>4%2
0

This is because 4/2=2 with no remainder.

>>>5%2
1

Because 5/2=2 with a remainder of 1.
This is why it makes sense to use it in our test, because a prime should not be divisible by a whole number integer evenly. If it does (if x==0) then the number is not prime and break is called which stops the loop there and starts again at the next value. The first 0 remainder we find is proof enough that that number is not a prime.


And that's as simple as it is, our for loop is nested within our while loop, every time the for loop finds another prime the counter for primes goes up and when it meets our requirement of 1000 it stops and prints the value. The reason for the -1 at the end would be because even after if finds the 1000th prime it finishes with the primeCheck+=1 which we have to negate at the end.


1000th Prime = 7919


Here is a list of the first 1000 primes if you want extra validation.
See more interesting Python below: