This post has already been read 1896 times!

Introduction

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 prime numbers are 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 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 for the very basic(brute force) approach is 
*/
function isPrime($n)
{
$i = 2;
if($n == 2) 
   return true;
while ($i < $n) 
{
  if ($n % $i == 0)
     return false;
  $i++;
}//end while
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 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;
}

Beside that these implementations shows how we can find prime number,
they are a very good example of how an algorithm can be optimized a lot with some small changes.

Comments are closed.

Post Navigation