daily pastebin goal
17%
SHARE
TWEET

Sieve of Eratosthenes in PHP

Bodigrim Nov 20th, 2011 1,022 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. <?php
  2.  
  3. define("LIMIT",1000000);
  4. define("SQRT_LIMIT",floor(sqrt(LIMIT)));
  5.  
  6. function classic(){
  7.         $sieve = array_fill(2,LIMIT-1,true);
  8.  
  9.         for($i=2;$i<=SQRT_LIMIT;$i++){
  10.                 if($sieve[$i]===true){
  11.                         for($j=$i*$i; $j<=LIMIT; $j+=$i){
  12.                                 $sieve[$j]=false;
  13.                                 }
  14.                         }
  15.                 }
  16.         //print_r($sieve);
  17.         }
  18.  
  19. function using_string(){
  20.         $sieve = str_repeat("\1", LIMIT+1);
  21.        
  22.         for($i=2;$i<=SQRT_LIMIT;$i++){
  23.                 if($sieve[$i]==="\1"){
  24.                         for($j=$i*$i; $j<=LIMIT; $j+=$i){
  25.                                 $sieve[$j]="\0";
  26.                                 }
  27.                         }
  28.                 }
  29.        
  30.         //$temp=array(); for($i=2;$i<=LIMIT;$i++) if(ord($sieve[$i])) $temp[]=$i; print_r($temp);
  31.         }
  32.  
  33.  
  34. function benchmark($func){
  35.         $memory0 = memory_get_peak_usage();
  36.         $time0   = microtime(TRUE);
  37.        
  38.         $func();
  39.        
  40.         $memory1 = memory_get_peak_usage();
  41.         $time1   = microtime(TRUE);
  42.        
  43.         $delta_mem  = $memory1 - $memory0;
  44.         $delta_time = $time1   - $time0;
  45.        
  46.         $bpe   = round($delta_mem / LIMIT, 2);
  47.         $mspe  = round(1000*$delta_time, 2);
  48.  
  49.         echo " $delta_mem b ($bpe b per element), $mspe ms ";  
  50.         }
  51.  
  52. // Now run
  53. benchmark("classic");
  54. // OR (not AND!)
  55. benchmark("using_string");
  56.  
  57. ?>
  58.  
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top