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 integer**s. 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