Is this a Prime Number?

Photo by Towfiqu barbhuiya on Unsplash

Is this a Prime Number?

Simple Approaches to Check for Prime

Tharindu Hasthika's photo
Tharindu Hasthika
·May 3, 2018·

3 min read

Subscribe to my newsletter and never miss my upcoming articles

Prime Numbers are an interesting set of numbers, there is no general expression to find a particular prime number. But when we are given a number to check for its primality, we can do it very easily (although we would need to do some serious computation for larger numbers). In this article I'll show you some methods of checking if a number is prime.

There are many ways of checking if a number is prime, below are some of them.

A Naive Approach

This is the most simple and straight forward way of checking primality.

def is_prime(n):

    # prime numbers >= 2
    if n <= 1:
        return False

    # loop i from 2 to n - 1
    for i in range(2, n):
        # if n is divisible by i and the remainder is 0
        # then it is surely not prime
        if n % i == 0:
            return False

    # if a factor was not found it is prime!
    return True

The Running Time: \(O(n)\)

So This in't that bad for small integers but if the number is a very large number, like ten or hundred million it would slow down.

So What can we do to reduce our running time?

A Slightlty Smart Approach

If you can remember your maths classes, you could have noticed that for every factor there is another factor that when multiplied together gives the number in question. More formally,

if \(a\) is a factor \(n\)

then there is some \(b\) such that \(a*b=n\)

So let's see some examples and figure out what can be done to make the algorithm faster.

For example lets take 20

  • \(1 * 20 = 20\)
  • \(2 * 10 = 20\)
  • \(4 * 5 = 20\)
  • \(5 * 4 = 20\)
  • \(10 * 2 = 20\)
  • \(20 * 1 = 20\)

As you can see we are finding the other factor which makes up the number in a separate step, which is unnecessary. So we only need to look for the first numbers that are less than or equal to \(\sqrt{n}\).

So with that intuition we could write a new function which is much more faster for larger numbers. While coding you should remember that finding the sqrt of a number is more costly that multiplication so we could say that \(i*i \leq n\).

def is_prime(n):

    # prime numbers >= 2
    if n <= 1:
        return False

    # loop i from 2 to sqrt(n)
    i = 2
    while i * i <= n:
        # if n is divisible by i and the remainder is 0
        # then it is surely not prime
        if n % i == 0:
            return False
        i += 1

    # if a factor was not found it is prime!
    return True

Some Optimizations to the Function

There are some other optimizations that can be applied to the function to reduce the running time even further.

Check if \(n\) is divisible by \(2\), and if \(n \ne 2\) then it is not prime.

If a number is not divisible by \(2\) then we can be sure that it will not be divisible by any other even number. So we can cut down the iteration count in half!

So with those Optimizations the final function is as follows.

def is_prime(n):

    # prime numbers >= 2
    if n <= 1:
        return False

    if n == 2:
        return True

    # reject all even numbers exept for 2
    if n % 2 == 0:
        return False

    # loop i from 3 to sqrt(n)
    i = 3
    while i * i <= n:
        # if n is divisible by i and the remainder is 0
        # then it is surely not prime
        if n % i == 0:
            return False
        # loop over odd numbers only
        i += 2

    # if a factor was not found it is prime!
    return True

Hope you find it useful!

Did you find this article valuable?

Support Tharindu Hasthika by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
 
Share this