object Main {
  def merge[A <% Ordered[A]](a: Stream[A], b: Stream[A]): Stream[A] = 
    // ** Both `a` and `b` assume to be strictly increasing. **
    (a.headOption, b.headOption) match {
      case (Some(x), Some(y)) if x < y => x #:: merge(a.tail, b)
      case (Some(x), Some(y)) if x > y => y #:: merge(a, b.tail)
      case (Some(x), Some(_)) => x #:: merge(a.tail, b.tail)
      case (_, None) => a
      case _ => b
    }
 
  def joinL[A <% Ordered[A]](xs: Stream[Stream[A]]): Stream[A] = 
    xs.head.head #:: merge(xs.head.tail, joinL(xs.tail))
 
  def minus[A <% Ordered[A]](a: Stream[A], b: Stream[A]): Stream[A] = 
    // ** Both `a` and `b` assume to be strictly increasing. **
    (a.headOption, b.headOption) match {
      case (Some(x), Some(y)) if x < y => x #:: minus(a.tail, b)
      case (Some(x), Some(y)) if x > y => minus(a, b.tail)
      case (Some(_), Some(_)) => minus(a.tail, b.tail)
      case _ => a
    }
 
  val primes: Stream[BigInt] = 2 #:: minus(Stream.iterate(3:BigInt)(_+1), 
          joinL(primes.map{p => Stream.iterate(p*p)(_+p)}))
 
  def main(args: Array[String]): Unit = {
    printExecutionTime { println(primes.take(100).mkString(", ")) }
    // => 2, 3, 5, 7, … , 541
    // => 18msec
 
    printExecutionTime { println(primes(9999)) }
    // => 104729
    // => 150msec
  }
 
  private def printExecutionTime(proc: => Unit) = {
    val start = System.currentTimeMillis
    proc
    println((System.currentTimeMillis - start) + "msec")
  }
}

b2JqZWN0IE1haW4gewogIGRlZiBtZXJnZVtBIDwlIE9yZGVyZWRbQV1dKGE6IFN0cmVhbVtBXSwgYjogU3RyZWFtW0FdKTogU3RyZWFtW0FdID0gCiAgICAvLyAqKiBCb3RoIGBhYCBhbmQgYGJgIGFzc3VtZSB0byBiZSBzdHJpY3RseSBpbmNyZWFzaW5nLiAqKgogICAgKGEuaGVhZE9wdGlvbiwgYi5oZWFkT3B0aW9uKSBtYXRjaCB7CiAgICAgIGNhc2UgKFNvbWUoeCksIFNvbWUoeSkpIGlmIHggPCB5ID0+IHggIzo6IG1lcmdlKGEudGFpbCwgYikKICAgICAgY2FzZSAoU29tZSh4KSwgU29tZSh5KSkgaWYgeCA+IHkgPT4geSAjOjogbWVyZ2UoYSwgYi50YWlsKQogICAgICBjYXNlIChTb21lKHgpLCBTb21lKF8pKSA9PiB4ICM6OiBtZXJnZShhLnRhaWwsIGIudGFpbCkKICAgICAgY2FzZSAoXywgTm9uZSkgPT4gYQogICAgICBjYXNlIF8gPT4gYgogICAgfQoKICBkZWYgam9pbkxbQSA8JSBPcmRlcmVkW0FdXSh4czogU3RyZWFtW1N0cmVhbVtBXV0pOiBTdHJlYW1bQV0gPSAKICAgIHhzLmhlYWQuaGVhZCAjOjogbWVyZ2UoeHMuaGVhZC50YWlsLCBqb2luTCh4cy50YWlsKSkKCiAgZGVmIG1pbnVzW0EgPCUgT3JkZXJlZFtBXV0oYTogU3RyZWFtW0FdLCBiOiBTdHJlYW1bQV0pOiBTdHJlYW1bQV0gPSAKICAgIC8vICoqIEJvdGggYGFgIGFuZCBgYmAgYXNzdW1lIHRvIGJlIHN0cmljdGx5IGluY3JlYXNpbmcuICoqCiAgICAoYS5oZWFkT3B0aW9uLCBiLmhlYWRPcHRpb24pIG1hdGNoIHsKICAgICAgY2FzZSAoU29tZSh4KSwgU29tZSh5KSkgaWYgeCA8IHkgPT4geCAjOjogbWludXMoYS50YWlsLCBiKQogICAgICBjYXNlIChTb21lKHgpLCBTb21lKHkpKSBpZiB4ID4geSA9PiBtaW51cyhhLCBiLnRhaWwpCiAgICAgIGNhc2UgKFNvbWUoXyksIFNvbWUoXykpID0+IG1pbnVzKGEudGFpbCwgYi50YWlsKQogICAgICBjYXNlIF8gPT4gYQogICAgfQoKICB2YWwgcHJpbWVzOiBTdHJlYW1bQmlnSW50XSA9IDIgIzo6IG1pbnVzKFN0cmVhbS5pdGVyYXRlKDM6QmlnSW50KShfKzEpLCAKICAgICAgICAgIGpvaW5MKHByaW1lcy5tYXB7cCA9PiBTdHJlYW0uaXRlcmF0ZShwKnApKF8rcCl9KSkKCiAgZGVmIG1haW4oYXJnczogQXJyYXlbU3RyaW5nXSk6IFVuaXQgPSB7CiAgICBwcmludEV4ZWN1dGlvblRpbWUgeyBwcmludGxuKHByaW1lcy50YWtlKDEwMCkubWtTdHJpbmcoIiwgIikpIH0KICAgIC8vID0+IDIsIDMsIDUsIDcsIOKApiAsIDU0MQogICAgLy8gPT4gMThtc2VjCgogICAgcHJpbnRFeGVjdXRpb25UaW1lIHsgcHJpbnRsbihwcmltZXMoOTk5OSkpIH0KICAgIC8vID0+IDEwNDcyOQogICAgLy8gPT4gMTUwbXNlYwogIH0KCiAgcHJpdmF0ZSBkZWYgcHJpbnRFeGVjdXRpb25UaW1lKHByb2M6ID0+IFVuaXQpID0gewogICAgdmFsIHN0YXJ0ID0gU3lzdGVtLmN1cnJlbnRUaW1lTWlsbGlzCiAgICBwcm9jCiAgICBwcmludGxuKChTeXN0ZW0uY3VycmVudFRpbWVNaWxsaXMgLSBzdGFydCkgKyAibXNlYyIpCiAgfQp9

c2lldmUgb2YgRXJhdG9zdGhlbmVzIGluIFNjYWxh

sieve of Eratosthenes in Scala