Blog

There are 2 best-optimised logic for the checking prime number. Here matter of optimised mean, minimising Iterations. let’s start doing both scenario’s.

• Iterate through all numbers from 2 to n/2 and every number in between (2 to n/2) check it divides n or not.
• if n divided then return false(0) otherwise true(1)

<?php 
// Iteration till n/2 

$isPrime = true;
$num = 13;

for($i = 2; $i <= ($num / 2); $i++)
{
	if($num % $i == 0) 
	{
	  $isPrime = false;
	}
}
if($isPrime == true)
{
	echo "$num is prime number";
}else{
	echo $num."  is not prime number";
}
?>

Result is : 13 is prime number

• Iterate through all numbers from 2 to square root of n and every number in between (2 to sqrt(n)) check it divides n or not.
• if n divided then return false(0) otherwise true(1)

<?php
// Iteration till Squire root of N sqrt(n) 
$isPrime = true;
$num = 21;
for($i = 2; $i <= sqrt($num); $i++)
{
	if($num % $i == 0) 
	{
	  $isPrime = false;
	}
}
if($isPrime == true)
{
	echo "$num is prime number";
}else{
	echo $num."  is not prime number";
}
?>

Result is : 21 is not prime number

Need to focus on the below points

• Here, false = Not Prime
  true = Prime
  
• Why we don’t start Iteration from 1 ?
  As per definition of Prime number is : in order for a positive integer to be prime, it must be divisible by exactly two positive integers. While 1 is obviously divisible by only one positive integer itself (1). Therefore, 1 is NOT a prime number because it does not satisfy the definition of a prime