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";
?>
About the author
- I am a web developer from Navi Mumbai. Mainly dealt with LAMP stack, now into Django and getting into Laravel and Cloud. Founder of nerul.in and gaali.in
Comments
Join the discussionNo comments yet. Be the first to comment.





