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

Simple check for square root in a loop using integers alone

Comments

More from this blog

Email validity checker using Google's JSON API for DNS over HTTPS (DoH) in Google Sheets

Getting picoclaw to work on Windows

The core use-case of TypeScript

Hashnode's GraphQL API for RSS feeds

make makemigrations work again

Command Palette

Comments

More from this blog