Tuesday, December 13, 2016

Python 3 Prime Number Checker

Doing basic math is good exercise when working out the details of a programming language.
This one is using Python to check for prime numbers from 2 up to whatever value we have chosen. In this example, it is up to 50, but you can choose whichever value you wish.

This is using Python 3.
If you're transitioning from Python 2 you can use this acronym to remember the basic differences.

DRIP
Division is true division 2/3 = 1.5
Range is a generator, and there is no more xrange.
Items will help you get to Dictionary elements, you do not need iteritems
Print() is a function and no longer a statement. you need those parens
   if you want to not print a newline, 
   instead of a comma, you need to use end="" You can put a character in the ""


Prime Number Checker

max = 51
print ("Prime numbers up to", max)
for i in range(2,max):
    #skip evens
    if i % 2 == 0:
        # 2 is our first prime number, print it out
        if i == 2:
            print (i, end=" ")
        continue
    # check each value is divisible by 3 up to the value being checked itself. (from 3 -> the value in question
    # if the value being checked it 9 then check 3,4,5,6,7,8,9
    # we don't need to check using 2 because we already excluded the even numbers above
    evennum=False
    for k in range (3,i):
        if i % k == 0:
            evennum=True
            break
    if evennum==True:
        continue
    else:
        print(i,end=" ")

But wait~ There's more.
If a number is not prime then it has factors and for each two factors, one of them is below the square-root of the value you are checking. We only care if one of the factors exists (which will make the value not prime. As a result, we only have to check the values up to the "floor" (truncated integer) of the square-root of the value we're checking.

Example. Let's look at 36 which is not prime (we'll ignore that it's an even number and won't ever show up on our list.

  sqrt(36) = 6
36 has other factors
2x18
3x12
4x9

If we find even one of these factors we know it's not prime.
See how the factors distribute themselves around the squart-root
One is always lower and the other is always higher than 6.

So instead of for k in range (3, i)
we can do for k in range(3, math.floor(math.sqrt(i))
Since we're now doing math functions, we need to include the math module.

Here is a good reference (scroll down):
http://stackoverflow.com/questions/5811151/why-do-we-check-up-to-the-square-root-of-a-prime-number-to-determine-if-it-is-pr

Here's the full code:
import math
max = 51
print ("Prime numbers up to", max)
for i in range(2,max):
    #skip evens
    if i % 2 == 0:
        # 2 is our first prime number, print it out
        if i == 2:
            print (i, end=" ")
        continue
    # check each value is divisible by 3 up to the value being checked
    # we don't need to check using 2 because we already excluded the even numbers above
    # NOTE we only need to check if there's a factor up to the square-root of the series
    # (See the text for an explanation)
    endval = math.floor(math.sqrt(i))
    evennum=False
    for k in range (3,endval):
        if i % k == 0:
            evennum=True
            break
    if evennum==True:
        continue
    else:
        print(i,end=" ")