fork download 
  1. <?php
  2.  
  3. // for PHP 5.3 or later
  4.  
  5. function primes($upto, $func){
  6.    if( $upto > 25000 ){ return large_primes($upto, $func); }
  7.    $upto -= 1;
  8.    $flags = array_fill(0, $upto-1, true);
  9.    for( $i = 0; $i < $upto; $i++ ){
  10.       if( $flags[$i] ){
  11.          $prime = $i + 2;
  12.          $k = $i + $prime;
  13.          while( $k < $upto ){
  14.             $flags[$k] = false;
  15.             $k += $prime;
  16.          }
  17.          $func($prime);
  18.       }
  19.    }
  20. }
  21.  
  22. function large_primes($upto, $func){
  23.    // The Algorithm is adapted from http://w...content-available-to-author-only...k.com/~jrm/printprimes.html
  24.    // This code is a translated version of Andreas Raab's #largePrimesUpTo:do: method
  25.    // which was written for the Squeak Smalltalk environment.
  26.  
  27.    $idx_limit = floor(sqrt($upto)) + 1;
  28.    $flags = array_fill(0, floor(($upto + 2309) / 2310) * 60 + 60, 0xFF);
  29.    $primes_up_to_2310 = array();
  30.    primes(2310, function($p) use(&$primes_up_to_2310){ array_push($primes_up_to_2310, $p); });
  31.    $mask_bit_idx = array_fill(0, 2310, 0);
  32.    $mask_bit_idx[0] = 0;
  33.    $mask_bit_idx[1] = 1;
  34.    $bit_idx = 1;
  35.    for( $i = 0; $i < 5; $i++ ){ $func($primes_up_to_2310[$i]); }
  36.    $idx = 5;
  37.    for( $n = 2; $n < 2310; $n++ ){
  38.       while( $primes_up_to_2310[$idx] < $n ){ $idx++; }
  39.       if( $n == $primes_up_to_2310[$idx] ){
  40.          $mask_bit_idx[$n] = ++$bit_idx;
  41.       } else if( $n % 2 == 0 || $n % 3 == 0 || $n % 5 == 0 || $n % 7 == 0 || $n % 11 == 0 ){
  42.          $mask_bit_idx[$n] = 0;
  43.       } else {
  44.          $mask_bit_idx[$n] = ++$bit_idx;
  45.       }
  46.    }
  47.    for( $n = 13; $n <= $upto; $n += 2 ){
  48.       if( $mask_bit = $mask_bit_idx[$n % 2310] ){
  49.          $byte_idx = floor($n / 2310) * 60 + ($mask_bit-1 >> 3);
  50.          $bit_idx = 1 << ($mask_bit & 7);
  51.          if( $flags[$byte_idx] & $bit_idx ){
  52.             $func($n);
  53.             if( $n < $idx_limit ){
  54.                $idx = $n * $n;
  55.                if( !($idx & 1) ){ $idx += $n; }
  56.                while( $idx <= $upto ){
  57.                   if( $mask_bit = $mask_bit_idx[$idx % 2310] ){
  58.                      $byte_idx = floor($idx / 2310) * 60 + ($mask_bit-1 >> 3);
  59.                      $mask_bit = 255 - (1 << ($mask_bit & 7));
  60.                      $flags[$byte_idx] = $flags[$byte_idx] & $mask_bit;
  61.                   }
  62.                   $idx += 2 * $n;
  63.                }
  64.             }
  65.          }
  66.       }
  67.    }
  68. }
  69.  
  70. $max = intval($argv[1]);
  71. if( !$max ){ $max = 100; }
  72. $q = $c = 0;
  73. primes($max, function($p) use(&$q, &$c){ $q = $p; $c++; });
  74. echo $q, " ", $c;
  75.  
Runtime error #stdin #stdout 0.02s 13664KB
comments (?)
stdin 
Standard input is empty
stdout 
Parse error: syntax error, unexpected T_FUNCTION in /home/Ya2pTz/prog.php on line 30
https://ideone.com/munh8
language:
PHP (php 7.3.5)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!