<?php
/**
* A really fast class to check if a number is a prime number. Basically, it
* looks at the number and checks its potential for being a prime number step
* by step. If it passes the fast initial sieve steps then it does the
* processor-intensive analysis to see if it is a real prime.
*
* Usage:
<code>
set_time_limit(0);
include 'IsPrime.php';
$number=164729;
echo (IsPrime::test($number)) ? "$number is prime" : "$number is not prime";
</code>
*
* @author Ahmad Retha 31/12/2011
* @license New BSD
* @version 2011123100 First!
* @version 2012010900 Optimization: Replaced '$i < ($num/2)' with '$i < sqrt($num)'; Thanks Jacq Fabien
* @version 2013062300 Bug fix; Thanks Omar Ramos
*/
class IsPrime
{
/**
* @param int $num
* @return bool
*/
public static function test($num)
{
//-n, 0, 1 not allowed
if ($num < 2)
return false;
//check for single digit primes
if (in_array($num, array(2, 3, 5, 7)))
return true;
//prime numbers end in 1, 3, 7 or 9 no matter how long they are
if (!in_array(substr($num, -1), array(1, 3, 7, 9)))
return false;
//if the number is divisible by 3 or 7 (very common) then it's not prime
if ($num%3 == 0 || $num%7 == 0)
return false;
/*
* Now find all the numbers up to the square root of potential prime
* number and test if they divide into it
*/
//the primes array holds prime numbers to test if they divide into num
$primes = array(2, 3, 5, 7);
for ($i = 11, $limit = sqrt($num); $i <= $limit; $i++) {
//if the number is divisible by a prime number then it's not prime
$isPrime = true;
foreach ($primes AS $prime) {
if ($i%$prime == 0) {
$isPrime = false;
break;
}
}
//check if the increment goes into our number
if ($isPrime) {
if ($num%$i == 0)
return false;
$primes[] = $i;
}
}
//$num is prime - divisible by itself and 1 only
return true;
}
}
|
Download
