fork download
  1. object Main {
  2. def primes(upto: Int, doFun: Int => Unit): Unit = {
  3. if (upto > 25000) return large_primes(upto, doFun)
  4. var limit = upto - 1
  5. var flags = new Array[Boolean](limit)
  6. for (i <- 0 until limit - 1) {
  7. if (!flags(i)) {
  8. var prime = i + 2
  9. var k = i + prime
  10. while (k < limit) {
  11. flags(k) = true
  12. k += prime
  13. }
  14. doFun(prime)
  15. }
  16. }
  17. }
  18.  
  19. def large_primes(upto: Int, doFun: Int => Unit): Unit = {
  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.  
  25. var limit = upto - 1
  26. var idx_limit = scala.math.sqrt(limit).toInt
  27.  
  28. var flags = (new Array[Int]((limit + 2309) / 2310 * 60 + 60)).map(_ => 0xFF)
  29.  
  30. var buf = new scala.collection.mutable.ArrayBuffer[Int]
  31. var i: Int = 0
  32. primes(2310, prime => buf += prime)
  33. var primes_up_to_2310 = buf.toArray
  34.  
  35. var mask_bit_idx = new Array[Int](2310)
  36. mask_bit_idx(0) = 0
  37. mask_bit_idx(1) = 1
  38. var bit_idx = 1
  39.  
  40. for (i <- 0 to 4) doFun(primes_up_to_2310(i))
  41.  
  42. var idx = 5
  43. for (n <- 2 to 2309) {
  44. while (primes_up_to_2310(idx) < n) idx += 1
  45. if (n == primes_up_to_2310(idx)) {
  46. bit_idx += 1
  47. mask_bit_idx(n) = bit_idx
  48. } else {
  49. if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0 || n % 11 == 0) {
  50. mask_bit_idx(n) = 0
  51. } else {
  52. bit_idx += 1
  53. mask_bit_idx(n) = bit_idx
  54. }
  55. }
  56. }
  57.  
  58.  
  59. for (n <- 13 to limit by 2) {
  60. var mask_bit = mask_bit_idx(n % 2310)
  61. if (mask_bit != 0) {
  62. var byte_idx = n / 2310 * 60 + (mask_bit - 1) / 8
  63. bit_idx = 1 << (mask_bit & 7)
  64. if ((flags(byte_idx) & bit_idx) != 0) {
  65. doFun(n)
  66. if (n < idx_limit) {
  67. idx = n * n
  68. if ((idx & 1) == 0) idx += n
  69. while (idx <= limit) {
  70. mask_bit = mask_bit_idx(idx % 2310)
  71. if (mask_bit != 0) {
  72. byte_idx = idx / 2310 * 60 + (mask_bit - 1) / 8
  73. mask_bit = 255 - (1 << (mask_bit & 7))
  74. flags(byte_idx) = flags(byte_idx) & mask_bit
  75. }
  76. idx += 2 * n
  77. }
  78. }
  79. }
  80. }
  81. }
  82. }
  83.  
  84. def main(args: Array[String]) {
  85. var max = 100
  86. if( args.length == 1 ){ max = args(0).toInt }
  87. var c = 0
  88. var q = 0
  89. var start = new java.util.Date().getTime
  90. primes(max, p => { q = p; c += 1 })
  91. println(q, c, new java.util.Date().getTime - start)
  92. }
  93. }
Success #stdin #stdout 0.29s 247360KB
stdin
Standard input is empty
stdout
(97,25,233)