## PHP | check prime number

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