# File: tests/prime.php

 Recommend this page to a friend!
 Classes of CPK Smithies bitvec tests/prime.php Download
File: tests/prime.php Example script text/plain Demo using bitvec to generate primes using sieve techniques bitvec Manipulate arrays of bits with SplFixedArray class By CPK Smithies Move from incorrect subdirectory 10 years ago 5,658 bytes

## Contents

 ``` v1.0  * @author cpks  * @license Public Domain  * @package prime  */ /**  * Set of prime numbers  *  * Outputs:  * - return whether a number is prime;  * - construct a list of prime numbers;  * - return biggest prime smaller than a number.  *  *************  * Use: *  *************  * - for finding if a number is prime: prime::is_prime(\$number);  * - for biggest prime number smaller than x:  * prime::smallerPrime(\$x);  * - for list of prime numbers smaller than x:  * \$p = new prime(\$x);  * OR, using sieve of Eratosthenes:  * \$e = new erato_prime(\$x);  * OR, using Atkin's sieve (a little slower):  * \$a = new atkin_prime(\$x);  * OR, using sieve of Sundaram (uses half as much memory):  * \$s = new sundaram_prime(\$x);  * @package prime  * @todo add an iterator to access the list and make primelist member private  */ class prime {   /*    * @var int[] array contains list of prime numbers    */   public \$primelist = array();   /**    * return whether a number is prime    *    * @param int \$number    * @return boolean    * @throws InvalidArgumentException    */   static public function is_prime(\$number) {     if (\$number < 2)       throw new InvalidArgumentException('Prime numbers start at 2.');     \$number = (int)\$number;     for (\$i = 2; \$i < floor(sqrt(\$number) + 1); ++\$i) {       if (!(\$number % \$i))         return FALSE;     }     return TRUE;   }   /**    * calculate biggest prime number smaller than \$number    *    * @param int \$number upper bound    * @return int    * @throws InvalidArgumentException    */   static public function smallerPrime(\$number) {     if (\$number <= 2)       throw new InvalidArgumentException('2 is smallest prime number');     for (\$i = \$number - 1; \$i > 1; --\$i)       if (self::is_prime(\$i)) return \$i;   }   /**    * generate list of prime numbers, computed by calculating if every number    * from list is prime    *    * @param int \$number upper bound    * @throws InvalidArgumentException    */   private function generate(\$number) {     \$this->primelist[] = 2;     \$this->primelist[] = 3;     for (\$i = 5; \$i < \$number; \$i += 2) { // (BUG: was originally =+2)       if (self::is_prime(\$i)) \$this->primelist[] = \$i;     }   }   /**    * Construct as a list of primes up to number supplied    *    * Use the generate method for the class    * @param int \$number upper bound    * @throws InvalidArgumentException if upper bound < 3    */   public function __construct(\$number) {     if (\$number <= 2)       throw new InvalidArgumentException('2 is smallest prime number');     \$this->generate(\$number);   }   /**    * Compare with another instance    * @param prime \$other    * @return bool TRUE if same    */   public function same_as(prime \$other) {     return \$this->primelist == \$other->primelist;   }   /**    * Dump to stdout for debug purposes    */   public function dump() {     echo implode(',', \$this->primelist) . PHP_EOL;   } } require_once 'bitvec.php'; /**  * Override generation to use the Eratosthenes sieve algorithm  * @package prime  */ class erato_prime extends prime {   /**    * generate list of prime numbers, computed with Eratosthenes sieve algorithm    *    * @param int \$number    */   private function generate(\$number) {     \$erat = new bitvec(\$number);     \$erat->setall();     for (\$i = 2; \$i < \$number; ++\$i) {       if (\$erat[\$i]) {         for (\$j = 2; \$j * \$i < \$number; ++\$j) \$erat[\$i * \$j] = 0;       }     }     for (\$i = 2; \$i < \$number; ++\$i) {       if (\$erat[\$i]) \$this->primelist[] = \$i;     }   } } /**  * Override generation to use the Atkin sieve algorithm  * @package prime  */ class atkin_prime extends prime {   /**    * generate list of prime numbers, computed with atkin sieve algorithm    *    * @param int \$number    */   private function generate(\$number) {     \$atkin = new bitvec(\$number);     for (\$i = 1; \$i < sqrt(\$number); ++\$i) {       for (\$j = 1; \$j < sqrt(\$number); ++\$j) {         \$x = 4 * \$i * \$i + \$j * \$j;         if (\$x < \$number && (\$x % 12 == 1 || \$x % 12 == 5))           \$atkin[\$x] = 1;         \$x = 3 * \$i * \$i + \$j * \$j;         if (\$x < \$number && \$x % 12 == 7)           \$atkin[\$x] = 1;         \$x = 3 * \$i * \$i - \$j * \$j;         if (\$i > \$j && \$x < \$number && \$x % 12 == 11)           \$atkin[\$x] = 1;       }     }     for (\$i = 5; \$i < sqrt(\$number); ++\$i) {       \$x = \$i * \$i;       \$j = 1;       while (\$j * \$x < \$number) {         \$atkin[\$j * \$x] = 0;         ++\$j;       }     }     \$atkin[2] = \$atkin[3] = 1;     for (\$i = 2; \$i < \$number; ++\$i) {       if (\$atkin[\$i]) \$this->primelist[] = \$i;     }   } } /**  * Override generation to use the Sundaram sieve algorithm  * @package prime  */ class sundaram_prime extends prime {   /**    * generate list of prime numbers, computed with Sundaram sieve algorithm    *    * @param int \$number    */   private function generate(\$number) {     \$number >>= 1;     \$sunda = new bitvec(\$number);     \$sunda->setall();     for (\$i = 1; \$i < \$number; ++\$i) {       \$denominator = (\$i << 1) + 1;       \$maxVal = (\$number - \$i) / \$denominator;       for (\$j = \$i; \$j < \$maxVal; ++\$j) \$sunda[\$i + \$j * \$denominator] = 0;     }     \$this->primelist[] = 2;     for (\$i = 1; \$i < \$number; ++\$i) if (\$sunda[\$i]) \$this->primelist[] = (\$i << 1) + 1;   } } ```
 About us Advertise on this site Site map Newsletter Statistics Site tips Privacy policy Contact
For more information send a message to `info at phpclasses dot org`.