fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(97,25,233)
https://ideone.com/nYlnD
language:
Scala (scala 2.12.8)
created:
11 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!