Login   Register  
PHP Classes
elePHPant
Icontem

File: tests/prime.php

Recommend this page to a friend!
Stumble It! Stumble It! Bookmark in del.icio.us Bookmark in del.icio.us
  Classes of CPK Smithies  >  bitvec  >  tests/prime.php  >  Download  
File: tests/prime.php
Role: Example script
Content type: text/plain
Description: Demo using bitvec to generate primes using sieve techniques
Class: bitvec
Manipulate arrays of bits with SplFixedArray class
Author: By
Last change: Move from incorrect subdirectory
Date: 1 year ago
Size: 5,658 bytes
 

Contents

Class file image Download
<?php
/******************************************************
 * Prime number checking and generation
 * @version 2.0
 * Adapted from:  Tzuly <tzulac@gmail.com> 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 $i $i $j $j;
        if (
$x $number && ($x 12 == || $x 12 == 5))
          
$atkin[$x] = 1;

        
$x $i $i $j $j;
        if (
$x $number && $x 12 == 7)
          
$atkin[$x] = 1;

        
$x $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;
  }
}