Prime number testing | Numerical Algorithms

A prime number is a number that is only divisible by 1 and the number itself. There are multiple ways we could test if a number is prime or not but today we will talk about two ways-

1. Naive method
2. sqrt(n) prime testing (the efficient method)

The Naive method
One method would be to check all possibilities from 2 to n - 1, n being the number we are testing. This would mean that if a number is prime we will have to search through all the numbers from 2 to n - 1. But if a number is not a prime then we will not have to search through all the possibilities, we will just return false if a number is completely divisible by another number that means it doesn't leave any remainder.

def isPrime(n):
    for i in range(2,n):
        if n%i==0:
            return False
    return True

The worst case for this method would be O(N).
Sqrt(n) method
Okay, so the logic behind this method is that every composite number has at least one factor that lies between 0 and the square root of n. Thus, we only check if it has a factor and if it does indeed have a factor, it's not a prime.

import math

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

First we check if the number is equal to or less than one. Then we check if the number is to 2 and return True. Next, we check if a number is even, if it is even, then it's not a prime. Then in the last step we go through all the odd numbers between 3 and the square root of if a number is divisible by an even number then it will be divisible by 2 which we check for in the previous step, if any number completely divides n we return False, else we return True. This algorithm has a worst case run time of O(sqrt(n)), which is a huge improvement over the naive algorithm.

For more tutorials on algorithms and data structures, subscribe to this blog and also explore this blog for other interesting tutorials.