Skip to main content

Simple check for square root in a loop using integers alone

Published 2 min readMarkdown

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

24 views

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

No comments yet. Be the first to comment.