fork download
  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
stdin
Standard input is empty
stdout
97 25 1