fork download
copy 
  1. sub primes {
  2.     my ($upto, $func) = @_;
  3.  
  4.     return large_primes($upto, $func) if $upto > 25000;
  5.     $upto -= 1;
  6.     my @flags = (1) x $upto;
  7.     foreach my $i (0..$upto - 1){
  8.         if ($flags[$i]){
  9.             my $prime = $i + 2;
  10.             my $k = $i + $prime;
  11.             while($k < $upto){
  12.                 $flags[$k] = 0;
  13.                 $k += $prime;
  14.             }
  15.             $func->($prime);
  16.         }
  17.     }
  18. }
  19.  
  20. sub large_primes {
  21.     my ($upto, $func) = @_;
  22.  
  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.     my $idx_limit = int(sqrt($upto)) + 1;
  28.     my @flags = (0xFF) x (int(($upto + 2309) / 2310) * 60 + 60);
  29.     my @primes_up_to_2310 = ();
  30.     primes(2310, sub{ push(@primes_up_to_2310, $_[0]) });
  31.     my @mask_bit_idx;
  32.     $#mask_bit_idx = 2309;
  33.     $mask_bit_idx[0] = 0;
  34.     $mask_bit_idx[1] = 1;
  35.     my $bit_idx = 1;
  36.     foreach my $i (0..4){
  37.         $func->($primes_up_to_2310[$i]);
  38.     }
  39.     my $idx = 5;
  40.     foreach my $n (2..2309){
  41.         $idx += 1 while $primes_up_to_2310[$idx] < $n;
  42.         if( $n == $primes_up_to_2310[$idx] ){
  43.             $mask_bit_idx[$n] = $bit_idx += 1;
  44.         }
  45.         elsif( $n % 2 == 0 || $n % 3 == 0 || $n % 5 == 0 || $n % 7 == 0 || $n % 11 == 0 ){
  46.             $mask_bit_idx[$n] = 0;
  47.         }
  48.         else {
  49.             $mask_bit_idx[$n] = $bit_idx += 1;
  50.         }
  51.     }
  52.     for( my $n = 13; $n <= $upto; $n += 2 ){
  53.         if( my $mask_bit = $mask_bit_idx[$n % 2310] ){
  54.             my $byte_idx = int($n / 2310) * 60 + ($mask_bit - 1 >> 3);
  55.             $bit_idx = 1 << ($mask_bit & 7);
  56.             if( $flags[$byte_idx] & $bit_idx ){
  57.                 $func->($n);
  58.                 if( $n < $idx_limit ){
  59.                     $idx = $n * $n;
  60.                     $idx += $n if !($idx & 1);
  61.                     while( $idx <= $upto ){
  62.                         if( $mask_bit = $mask_bit_idx[$idx % 2310] ){
  63.                             $byte_idx = int($idx / 2310) * 60 + ($mask_bit-1 >> 3);
  64.                             $mask_bit = 255 - (1 << ($mask_bit & 7));
  65.                             $flags[$byte_idx] = $flags[$byte_idx] & $mask_bit;
  66.                         }
  67.                         $idx += 2 * $n;
  68.                     }
  69.                 }
  70.             }
  71.         }
  72.     }
  73. }
  74.  
  75. my $max = @ARGV == 1 ? $ARGV[0] : 100;
  76. my $q = 0;
  77. my $c = 0;
  78. primes($max, sub{ $q = $_[0]; $c += 1; });
  79. print $q, " ", $c, "\n";
Success #stdin #stdout 0s 4552KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
97 25
https://ideone.com/DNfDq
language:
Perl (perl 5.28.1)
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!