fork download
copy 
  1. function primes(upto, func){
  2.    if( upto > 25000 ){ return large_primes(upto, func); }
  3.    upto -= 1;
  4.    var flags = new Array(upto);
  5.    for( i = 0; i < upto; i++){ flags[i] = true; }
  6.    for( i = 0; i < upto; i++){
  7.       if( flags[i] ){
  8.          var prime = i + 2;
  9.          var k = i + prime;
  10.          while( k < upto ){
  11.             flags[k] = false;
  12.             k += prime;
  13.          }
  14.          func(prime);
  15.       }
  16.    }
  17. }
  18.  
  19. function large_primes(upto, func){
  20.    // The Algorithm is adapted from http://w...content-available-to-author-only...k.com/~jrm/printprimes.html
  21.    // This code is a translated version of Andreas Raab's #largePrimesUpTo:do: method
  22.    // which was written for the Squeak Smalltalk environment.
  23.  
  24.    var idx_limit = Math.floor(Math.sqrt(upto)) + 1;
  25.    var flags = new Array(Math.floor((upto + 2309) / 2310) * 60 + 60);
  26.    for( i = 0; i < flags.length; i++){ flags[i] = 0xFF; }
  27.    var primes_up_to_2310 = [];
  28.    primes(2310, function(p){ primes_up_to_2310.push(p); });
  29.    var mask_bit_idx = new Array(2310);
  30.    mask_bit_idx[0] = 0;
  31.    mask_bit_idx[1] = 1;
  32.    var bit_idx = 1;
  33.    for( i = 0; i < 5; i++ ){ func(primes_up_to_2310[i]); }
  34.    var idx = 5;
  35.    for( n = 2; n < 2310; n++ ){
  36.       while( primes_up_to_2310[idx] < n ){ idx += 1; }
  37.       if( n == primes_up_to_2310[idx] ){
  38.          mask_bit_idx[n] = bit_idx += 1;
  39.       } else if( n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0 || n % 11 == 0 ){
  40.          mask_bit_idx[n] = 0;
  41.       } else {
  42.          mask_bit_idx[n] = bit_idx += 1;
  43.       }
  44.    }
  45.    for( n = 13; n <= upto; n += 2 ){
  46.       if( mask_bit = mask_bit_idx[n % 2310] ){
  47.          byte_idx = Math.floor(n / 2310) * 60 + (mask_bit-1 >> 3);
  48.          bit_idx = 1 << (mask_bit & 7);
  49.          if( flags[byte_idx] & bit_idx ){
  50.             func(n);
  51.             if( n < idx_limit ){
  52.                idx = n * n;
  53.                if( !(idx & 1) ){ idx += n; }
  54.                while( idx <= upto ){
  55.                   if( mask_bit = mask_bit_idx[idx % 2310] ){
  56.                      byte_idx = Math.floor(idx / 2310) * 60 + (mask_bit-1 >> 3);
  57.                      mask_bit = 255 - (1 << (mask_bit & 7));
  58.                      flags[byte_idx] = flags[byte_idx] & mask_bit;
  59.                   }
  60.                   idx += 2 * n;
  61.                }
  62.             }
  63.          }
  64.       }
  65.    }
  66. }
  67.  
  68. var max = 100;
  69. try{
  70.    if( process.argv.length == 3 ){ max = parseInt(process.argv[2]); }
  71. } catch(e){}
  72.  
  73. var start = new Date();
  74. var q = 0;
  75. var c = 0;
  76. primes(max, function(p){ q = p; c += 1; })
  77. var t = new Date() - start;
  78. try{ console.log(q, c, t) } catch(e){ print(q, c, t); }
Success #stdin #stdout 0.01s 5100KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
97 25 1
https://ideone.com/acfaZ
language:
JavaScript (SMonkey 60.2.3)
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!