How to Test for Primes Using Square Roots and Python

Free Image from Pixabay

Finding Prime Numbers

Prime numbers are very important, yet many students do not see the value of learning them. Primes have several applications, most importantly in information technology, such as public-key cryptography, which relies on the difficulty of factoring large numbers into their prime factors. One key challenge is to find prime numbers. Interestingly, Prime numbers and their properties were first studied extensively by the ancient Greek mathematicians. Euclid, for example, proved that there are infinitely many prime numbers. 

Just to refresh our memory, a number greater than 1 is called a prime number, if it has only two factors, namely 1 and the number itself. 

Proof by Contradiction

One of the first known proofs is the method of contradiction. It is used to calculate prime factors of large numbers. Calculating prime factors of small numbers is easy. For example, the factors of 17 is 1 and 17, so it is a prime number. What about large numbers? Let's look at the proof by contradiction method.

If a number n is not a prime, it can be factored into two factors a and b, such that n = a*b. For example, let's say a * b = 100, for various pairs of a and b.

If a = b, then they are equal, we have a*a = 100, or a^2 = 100, or a = 10, the square root of 100. If one of the numbers is less than 10, then the other has to be greater to make it to 100. For example, take 4 x 25 = 100. 4 is less than 10, the other number has to be greater than 10. In other words, if a * b, if one of them goes down, the other number has to get bigger to compensate so the product stays at 100. Put mathematically, the numbers revolve around the square root of their product. 

Let's test if 101 is prime number. You could start dividing 101 by 2, 3, 5, 7, etc, but that is very tedious. A better way is to take the square root of 101, which is roughly equal to 10.049875621. So you only need to try the integers up through 10, including 10. 8, 9, and 10 are not themselves prime, so you only have to test up through 7, which is prime.
​
Because if there's a pair of factors with one of the numbers bigger than 10, the other of the pair has to be less than 10. If the smaller one doesn't exist, there is no matching larger factor of 101. 

Let's now build an algorithm using this method to test any number for primality. 

Algorithm in Python

import math

def isPrime(num):
     if (num < 2):
         return False
     else:
         for i in range(2, int(math.sqrt(num)) + 1):
             if num % i == 0:
                   return False
         return True


print(isPrime(33))
print(isPrime(0))
print(isPrime(47))
print(isPrime(1047))
print(isPrime(11))
print(isPrime(59392847))

N.B: Do not just copy the code because you have to be careful with indentation in python.

Try the above algorithm and let us know if you found it useful or have alternative solutions.