Advertisement
Bodigrim

Sieve of Eratosthenes in PHP

Nov 20th, 2011
1,523
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
PHP 1.08 KB | None | 0 0
  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.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement