<?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:
set_time_limit(0);
include 'IsPrime.php';
$number=164729;
echo (IsPrime::test($number)) ? "$number is prime" : "$number is not prime";
*
* @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
*/
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 then it's not prime
if($num%3==0 || $num%7==0)
return FALSE;
/*
* Now find all the numbers up to the potential prime number / 2
* 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=10; $i < sqrt($num); $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;
}
}
if($isprime){
//check the prime number doesn't go into our number
if($num%$i == 0)
return FALSE;
$primes[] = $i;
}
}
//$num is prime - divisible by itself and 1 only
return TRUE;
}
}
|
Stumble It!
Bookmark in del.icio.us
Download
