Naïve integer primality calculator in PHP

Bismillaahir Rahmaanir Raheem

Alhamdulillaah, while reading about integers and, subsequently, prime numbers last night, I decided the time had come for me to write a primality calculator in PHP.  The test I use in my implementation is about as a naïve as one can possible get, but it was fun, nonetheless.

Interestingly enough, I discovered that there already exists a primality calculator for *nix-based systems – primes.  It comes with the bsd-games package for Fedora.  I assume the same is true for other distributions.  Mine isn’t quite as fast yet…but it does accept, optionally, one or two arguments. If there are two arguments, then it will calculate all primes starting from the first going until the second. If there is only one argument, it will calculate from PRIME_START (defined to be 2) through to the largest integer PHP can handle on your platform (usually the maximum value of a signed int on your machine).

There are loads of potential optimizations that can be performed, and this was just something written on a whim as a proof of concept. It seems to be accurate, however. The code, released under the GNU GPL v. 3.0, can be found below.

#!/usr/bin/php
< ?php

define('PRIME_START', 2);   //  One, by definition, is not prime

if (isset($argv[2])) {
    $start = (int) $argv[1];
    $max = (int) $argv[2];
} elseif (isset($argv[1])) {
    $start = (int) PRIME_START;
    $max = (int) $argv[1];
} else {
    $start = PRIME_START;
    $max = PHP_INT_MAX;
}

if ($start < PRIME_START) {
    $start = PRIME_START;
}

if ($max < PRIME_START) {
    $max = PHP_INT_MAX;
}

echo "Using $start as start value and $max as max value\n";

$int = $start;

while ($int < $max) {
    $start_time = microtime(true);
    if (is_prime($int)) {
        $total_time = round((microtime(true) - $start_time), 2);
        echo "$int is prime (calculated in {$total_time}s)\n";
    }
    ++$int;
}

echo "All possible primes lower than $max have been calculated!\n";

/**
 * A very naïve test to determine the primality of a given integer
 *
 * @param int $int
 * @return boolean integer is prime
 */
function is_prime($int)
{
    if (! is_numeric($int)) {
        return false;
    }

    $int = (int) $int;

    $test_divisor = PRIME_START; //  By coincidence, the first divisor to determine prime numbers is also the first prime number

    while ($test_divisor < $int) {
        if (is_divisor($int, $test_divisor)) {
            return false;
        }
        ++$test_divisor;
    }

    //  If we are here, then that means no divisors were found
    return true;
}

/**
 * Very simple function to determine if one integer is the divisor of another
 *
 * @param int $dividend
 * @param int $divisor
 * @return boolean $divisor is divisor of dividend
 */
function is_divisor($dividend, $divisor)
{
    if (0 === $dividend % $divisor) {
        return true;
    } else {
        return false;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *