Simple check for square root in a loop using integers alone
There was a situation where I couldn't get to use decimal / floating numbers in a variable or like in sqrt($n)
.
To check for a prime number, we need to check all odd numbers till the square root of a number for modulus 0. If n mod i
is zero then it's not prime.
This checks until sqrt($n)
which is mostly has a fraction which was I couldn't make use of.
<?php
$n = 101;
$isPrime = TRUE;
if ($n % 2 == 0) $isPrime = FALSE;
for ($i = 3; $i <= sqrt($n); $i += 2)
{
if ($n % $i == 0)
{
$isPrime = FALSE;
}
}
if ($isPrime)
echo "$n is Prime\n";
else
echo "$n is not Prime\n";
?>
So we have to check till n
which is waste of iterations. So, instead, we can break the loop if the square of the looping variable (which still will be an integer) is greater than n
.
<?php
$n = 101;
$isPrime = TRUE;
if ($n % 2 == 0) $isPrime = FALSE;
for ($i = 3; $i < $n; $ i+= 2)
{
if ($i * $i >= $n) break; # This is the check
if ($n % $i == 0)
{
$isPrime = FALSE;
}
}
if ($isPrime)
echo "$n is Prime\n";
else
echo "$n is not Prime\n";
?>