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:

The While Loop in Python

The while loop says that while one thing is true, do something. Here we can count to ten:

counter=0
while counter < 11:
 print(counter)
 counter=counter+1

What did we do here? First we initilized counter as 0, this is where our counter is starting. It is important to initialize the variable you are using in your while loop outside of the loop. After we have initialized counter to 0 we say: While the value of counter is less than 11, do something. In our case, do something is print(counter), which the first time through would be 0, and then we set counter equal to itself plus one.

Our loop will now continue with counter as 1 print one and add 1 to itself. When counter is equal to 10, it goes through one last time, prints 10 adds one to 11 and then passes through the while test again. This time it is not less than 11, because it equals 11 and so it stops. Your output should be:

0
1
2
3
4
5
6
7
8
9
10

We can say this same thing but, in my opinion, make it look nicer. We can do this by making use of multiple operators. The first example will be in line 2, instead of < 11, we can use <=10, which is less than or equal to. A list of such comparison operators is:

<=     If left operand is less than or equal to right operand, condition is true.

>=     If left operand is greater than or equal to right operand, condition is true

==     If left operand is equal to right operand, condition is true.

!=      If left operand is not equal to right operand, condition is true.

Notice the difference between the assignment operator = and the conditional operator ==. The first makes one operand equal another, the other tests the equality of the two operands. 

The second way we can simplify the program is by using the compound assignment operator +=. In line 4, where we say counter=counter+1, the same thing could be said with the expression, counter+=1. This takes the value of counter, adds one and assigns that value to counter. You can see how this be of use. Here are some more compound assignment operators:

+=  Adds left and right operand and assigns total to left operand
-= Subracts right from left operand and assigns total to left operand

*=Multiplies left and right operand and assigns total to left operand
/= Divides right from left operand and assigns total to left operand
**= Takes left operand to the power of the right operand and assigns total to left operand
%= Finds remainder of division between left operand and right operand, and assigns total to left operand.
//= Performs integer division between left and right operand and assigns total to left operand.

Our "improved" code would now be:


counter=0
while counter <= 10:
 print(counter)
 counter+=1