Each natural number that is divisible only by 1 and itself is prime. Prime numbers appear to be more interesting to humans than other numbers. Why is that and why are prime numbers more important than the numbers that are divisible by 2, for instance?

Perhaps the answer is that prime numbers are largely used in cryptography, although they were interesting for the ancient Egyptians and Greeks (Euclid has proved that the prime numbers are infinite circa 300 BC). The problem is that there is not a formula that can tell us which is the next prime number, although there are algorithms that check whether a given natural number is prime. It’s very important for these algorithms to be very effective, especially for big numbers.

## Overview

As I said, each natural number that is divisible only by 1 and itself is prime. That means that 2 is the first prime number and 1 is not considered prime. It’s easy to say that 2, 3, 5 and 7 are prime numbers, but what about 983? Well, yes 983 is prime, but how do we check that?

If we want to know whether **n** is prime the very basic approach is to check every single number between 2 and n. It’s kind of a brute force.

## Implementation

The basic implementation in PHP for the very basic (brute force) approach is as follows.

function isPrime($n) { $i = 2; if ($n == 2) { return true; } while ($i < $n) { if ($n % $i == 0) { return false; } $i++; } return true; } // prints the prime numbers between 2 and 100 // 3, 5, 7, ..., 97 for ($i = 3; $i < 100; $i++) { if (isPrime($i)) { echo $i; } }

Unfortunately this is one very ineffective algorithm. We don’t have
to check every single number between 1 and n, it’s enough to check only
the numbers between 1 and n/2-1. If we find such a divisor that will be
enough to say that **n** isn’t prime.

function isPrime($n) { $i = 2; if ($n == 2) { return true; } while ($i <= $n/2) { if ($n % $i == 0) { return false; } $i++; } return true; }

Although that code above optimizes a lot from our first prime checker, it’s clear that for large numbers it won’t be very effective.

Indeed checking against the interval [2, n/2 -1] isn’t the optimal
solution. A better approach is to check against [2, sqrt(n)]. This is
correct, because if **n** isn’t prime it can be represented
as p*q = n. Of course if p > sqrt(n), which we assume can’t be true,
that will mean that q < sqrt(n).

function isPrime($n) { $i = 2; if ($n == 2) { return true; } $sqrtN = sqrt($n); while ($i <= $sqrtN) { if ($n % $i == 0) { return false; } $i++; } return true; }

Besides the fact that these implementations show how we can find a prime number, they are a very good example of how an algorithm can be greatly optimized with some small changes.

### Sieve of Eratosthenes

Although the sieve of Eratosthenes isn’t the exact same approach (to
check whether a number is prime) it can give us a list of prime numbers
quite easily. To remove numbers that aren’t prime, we start with 2 and
we remove every single item from the list that is divisible by two. Then
we check for the rest of the items of the list, as shown on the picture below.

The PHP implementation of the Eratosthenes sieve isn’t difficult.

function eratosthenes_sieve(&$sieve, $n) { $i = 2; while ($i <= $n) { if ($sieve[$i] == 0) { echo $i; $j = $i; while ($j <= $n) { $sieve[$j] = 1; $j += $i; } } $i++; } } $n = 100; $sieve = array_fill(0, $n, 0); // 2, 3, 5, 7, ..., 97 eratosthenes_sieve($sieve, $n);

## Application

As I said prime numbers are widely used in cryptography, so they are always of a greater interest in computer science. In fact every number can be represented by the product of two prime numbers and that fact is used in cryptography as well. That’s because if we know that number, which is usually very very big, it is still very difficult to find out what are its prime multipliers.

Unfortunately the algorithms in this article are very basic and can be handy only if we work with small numbers or if our machines are tremendously powerful. Fortunately in practice there are more complex algorithms for finding prime numbers. Such are the sieves of Euler, Atkin and Sundaram.

## Comments

## Paul Russel replied on Sun, 2012/06/10 - 9:19am

## Sonia Jain replied on Sat, 2013/12/07 - 2:46am in response to: Paul Russel

Yes, I will change the above function by i++ to i+=2 so that it will reduce the number time it goes for loop as any evn number apart from 2 doesn't qualify for prime number

## Prasad Srinivas replied on Fri, 2014/10/10 - 5:53pm in response to: Sonia Jain

Hi Guys,

I am very poor in Algorithms, but my intention of learning algorithms increased in recent days. Now i have commited to learn to give best solution for any problem. So, here in validating a number is prime or not, i have seen caluculating square root of the number and iteration between 2 and square root of number. Here i dont understand what is the logic behind, if any number less than square root of input is divisible, then its not prime. Please somebody explain this logic how it will happen.