Anjanesh Lekshminarayanan
Anjanesh

Anjanesh

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";
?>
 
Share this