fork download 
  1. // from http://stackoverflow.com/questions/20985539/scala-erastothenes-is-there-a-straightforward-way-to-replace-a-stream-with-an/20991776
  2.  
  3. object Main extends App {
  4.   def primes(): Iterator[Long] = {
  5.     // generic class as a Co Inductive Stream element
  6.     class CIS[A](val v: A, val cont: () => CIS[A])
  7.  
  8.     def mltpls(p: Long): CIS[Long] = {
  9.       var px2 = p * 2
  10.       def nxtmltpl(cmpst: Long): CIS[Long] =
  11.         new CIS(cmpst, () => nxtmltpl(cmpst + px2))
  12.       nxtmltpl(p * p)
  13.     }
  14.     def allMltpls(mps: CIS[Long]): CIS[CIS[Long]] =
  15.       new CIS(mltpls(mps.v), () => allMltpls(mps.cont()))
  16.     def merge(a: CIS[Long], b: CIS[Long]): CIS[Long] =
  17.       if (a.v < b.v) new CIS(a.v, () => merge(a.cont(), b))
  18.       else if (a.v > b.v) new CIS(b.v, () => merge(a, b.cont()))
  19.       else new CIS(b.v, () => merge(a.cont(), b.cont()))
  20.     def pairs(mltplss: CIS[CIS[Long]]): CIS[CIS[Long]] = {
  21.       val tl = mltplss.cont()
  22.       new CIS(merge(mltplss.v, tl.v), () => pairs(tl.cont()))
  23.     }
  24.     def mrgMltpls(mlps: CIS[CIS[Long]]): CIS[Long] =
  25.       new CIS(mlps.v.v, () => merge(mlps.v.cont(), mrgMltpls(pairs(mlps.cont()))))
  26.     def minusStrtAt(n: Long, cmpsts: CIS[Long]): CIS[Long] =
  27.       if (n < cmpsts.v) new CIS(n, () => minusStrtAt(n + 2, cmpsts))
  28.       else minusStrtAt(n + 2, cmpsts.cont())
  29.     // the following are recursive, where cmpsts uses oddPrms and
  30.     // oddPrms uses a delayed version of cmpsts in order to avoid a race
  31.     // as oddPrms will already have a first value when cmpsts is called to generate the second
  32.     def cmpsts(): CIS[Long] = mrgMltpls(allMltpls(oddPrms()))
  33.     def oddPrms(): CIS[Long] = new CIS(3, () => minusStrtAt(5L, cmpsts()))
  34.     Iterator.iterate(new CIS(2L, () => oddPrms()))
  35.                      {(cis: CIS[Long]) => cis.cont()}
  36.       .map {(cis: CIS[Long]) => cis.v}
  37.   }
  38.  
  39.   print(primes().drop(99999).next())
  40. }
  41. // 0.37 seconds and 322K for 100
  42. // 0.45 seconds and 322K for 10000
  43. // 0.76 seconds and 322K for 100000
  44. // 5.13 seconds and 322K for 1000000 for performance of about 1.09
Success #stdin #stdout 0.77s 322240KB
comments (?)
stdin 
Standard input is empty
stdout 
1299709
https://ideone.com/DwhQ1f
Tree Folding Prime Sieve (incremental Sieve of Eratosthenes) completely functional
language:
Scala (scala 2.12.8)
created:
9 years ago
visibility:
secret

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!