Python Primality Test (Square root vs Integer up to x )

primalityReadme.md

PRIMALITY TEST (TIME COMPLEXITY)

Testing all integers to squareroot vs testing all integers to x

It took the first algorithm 6.35099983215 seconds to find out if 30313411 is a prime number It took the second algorithm 0.000999927520752 seconds. Difference in time is 6.349999904629248 seconds

prime.py

"""
A not so efficient algorithm
"""
import time
def isPrimeNumber(n):
    startTime = time.time()
    # First we check if the number is less than 2 and if so, it cannot be prime
    if n < 2:
        return False
    #If the number is equal to or greater than two?
    else:
        # if it is two then it is a prime number
        if n == 2:
            return True
        #If it is greater than 2 then we do more checking
        else:
            # we generate a list of number up to that integer n
            for i in range(2, n):
                # if any of the number is up to that range is divisible by n then it is not a prime number
                if n % i == 0:
                    print time.time() - startTime
                    return False
            # Otherwise, yes, we have got our prime number!
            print time.time() - startTime
            return True
print isPrimeNumber(30313411)

# 30313411 is a prime number.
# Running time is 6.35099983215

prime2.py

"""
A better algorithm
"""
import time
import math
def isPrime(x):
    startTime = time.time()
    # If number is less than 2 then return False
    if x < 2:
        return False
    # Otherwise, divide x repeatedly(modulo) by each number up to its squareroot
    for i in range(2, int(math.sqrt(x)) + 1):
        # If any of the number in that range evenly divides x then it is not prime
        if x % i == 0:
            print time.time() - startTime
            return False
    # If not, then it is prime
    print time.time() - startTime
    return True            
print isPrime(30313411)
# 30313411 is a prime number.
# Running time is 0.000999927520752