// from http://stackoverflow.com/questions/20985539/scala-erastothenes-is-there-a-straightforward-way-to-replace-a-stream-with-an/20991776
 
object Main extends App {
  def primes(): Iterator[Long] = {
    // generic class as a Co Inductive Stream element
    class CIS[A](val v: A, val cont: () => CIS[A])
 
    def mltpls(p: Long): CIS[Long] = {
      var px2 = p * 2
      def nxtmltpl(cmpst: Long): CIS[Long] =
        new CIS(cmpst, () => nxtmltpl(cmpst + px2))
      nxtmltpl(p * p)
    }
    def allMltpls(mps: CIS[Long]): CIS[CIS[Long]] =
      new CIS(mltpls(mps.v), () => allMltpls(mps.cont()))
    def merge(a: CIS[Long], b: CIS[Long]): CIS[Long] =
      if (a.v < b.v) new CIS(a.v, () => merge(a.cont(), b))
      else if (a.v > b.v) new CIS(b.v, () => merge(a, b.cont()))
      else new CIS(b.v, () => merge(a.cont(), b.cont()))
    def mrgMltpls(mlps: CIS[CIS[Long]]): CIS[Long] =
      new CIS(mlps.v.v, () => merge(mlps.v.cont(), mrgMltpls(mlps.cont())))
    def minusStrtAt(n: Long, cmpsts: CIS[Long]): CIS[Long] =
      if (n < cmpsts.v) new CIS(n, () => minusStrtAt(n + 2, cmpsts))
      else minusStrtAt(n + 2, cmpsts.cont())
    // the following are recursive, where cmpsts uses oddPrms and
    // oddPrms uses a delayed version of cmpsts in order to avoid a race
    // as oddPrms will already have a first value when cmpsts is called to generate the second
    def cmpsts(): CIS[Long] = mrgMltpls(allMltpls(oddPrms()))
    def oddPrms(): CIS[Long] = new CIS(3, () => minusStrtAt(5L, cmpsts()))
    Iterator.iterate(new CIS(2L, () => oddPrms()))
                     {(cis: CIS[Long]) => cis.cont()}
      .map {(cis: CIS[Long]) => cis.v}
  }
 
  print(primes().drop(99999).next())
}
// 0.36 seconds and 322K for 100
// 0.41 seconds and 322K for 10000
// 1.29 seconds and 322K for 100000
// 12.37 seconds and 322K for 600000 for performance of about 1.43

Ly8gZnJvbSBodHRwOi8vc3RhY2tvdmVyZmxvdy5jb20vcXVlc3Rpb25zLzIwOTg1NTM5L3NjYWxhLWVyYXN0b3RoZW5lcy1pcy10aGVyZS1hLXN0cmFpZ2h0Zm9yd2FyZC13YXktdG8tcmVwbGFjZS1hLXN0cmVhbS13aXRoLWFuLzIwOTkxNzc2CgpvYmplY3QgTWFpbiBleHRlbmRzIEFwcCB7CiAgZGVmIHByaW1lcygpOiBJdGVyYXRvcltMb25nXSA9IHsKICAgIC8vIGdlbmVyaWMgY2xhc3MgYXMgYSBDbyBJbmR1Y3RpdmUgU3RyZWFtIGVsZW1lbnQKICAgIGNsYXNzIENJU1tBXSh2YWwgdjogQSwgdmFsIGNvbnQ6ICgpID0+IENJU1tBXSkKCiAgICBkZWYgbWx0cGxzKHA6IExvbmcpOiBDSVNbTG9uZ10gPSB7CiAgICAgIHZhciBweDIgPSBwICogMgogICAgICBkZWYgbnh0bWx0cGwoY21wc3Q6IExvbmcpOiBDSVNbTG9uZ10gPQogICAgICAgIG5ldyBDSVMoY21wc3QsICgpID0+IG54dG1sdHBsKGNtcHN0ICsgcHgyKSkKICAgICAgbnh0bWx0cGwocCAqIHApCiAgICB9CiAgICBkZWYgYWxsTWx0cGxzKG1wczogQ0lTW0xvbmddKTogQ0lTW0NJU1tMb25nXV0gPQogICAgICBuZXcgQ0lTKG1sdHBscyhtcHMudiksICgpID0+IGFsbE1sdHBscyhtcHMuY29udCgpKSkKICAgIGRlZiBtZXJnZShhOiBDSVNbTG9uZ10sIGI6IENJU1tMb25nXSk6IENJU1tMb25nXSA9CiAgICAgIGlmIChhLnYgPCBiLnYpIG5ldyBDSVMoYS52LCAoKSA9PiBtZXJnZShhLmNvbnQoKSwgYikpCiAgICAgIGVsc2UgaWYgKGEudiA+IGIudikgbmV3IENJUyhiLnYsICgpID0+IG1lcmdlKGEsIGIuY29udCgpKSkKICAgICAgZWxzZSBuZXcgQ0lTKGIudiwgKCkgPT4gbWVyZ2UoYS5jb250KCksIGIuY29udCgpKSkKICAgIGRlZiBtcmdNbHRwbHMobWxwczogQ0lTW0NJU1tMb25nXV0pOiBDSVNbTG9uZ10gPQogICAgICBuZXcgQ0lTKG1scHMudi52LCAoKSA9PiBtZXJnZShtbHBzLnYuY29udCgpLCBtcmdNbHRwbHMobWxwcy5jb250KCkpKSkKICAgIGRlZiBtaW51c1N0cnRBdChuOiBMb25nLCBjbXBzdHM6IENJU1tMb25nXSk6IENJU1tMb25nXSA9CiAgICAgIGlmIChuIDwgY21wc3RzLnYpIG5ldyBDSVMobiwgKCkgPT4gbWludXNTdHJ0QXQobiArIDIsIGNtcHN0cykpCiAgICAgIGVsc2UgbWludXNTdHJ0QXQobiArIDIsIGNtcHN0cy5jb250KCkpCiAgICAvLyB0aGUgZm9sbG93aW5nIGFyZSByZWN1cnNpdmUsIHdoZXJlIGNtcHN0cyB1c2VzIG9kZFBybXMgYW5kCiAgICAvLyBvZGRQcm1zIHVzZXMgYSBkZWxheWVkIHZlcnNpb24gb2YgY21wc3RzIGluIG9yZGVyIHRvIGF2b2lkIGEgcmFjZQogICAgLy8gYXMgb2RkUHJtcyB3aWxsIGFscmVhZHkgaGF2ZSBhIGZpcnN0IHZhbHVlIHdoZW4gY21wc3RzIGlzIGNhbGxlZCB0byBnZW5lcmF0ZSB0aGUgc2Vjb25kCiAgICBkZWYgY21wc3RzKCk6IENJU1tMb25nXSA9IG1yZ01sdHBscyhhbGxNbHRwbHMob2RkUHJtcygpKSkKICAgIGRlZiBvZGRQcm1zKCk6IENJU1tMb25nXSA9IG5ldyBDSVMoMywgKCkgPT4gbWludXNTdHJ0QXQoNUwsIGNtcHN0cygpKSkKICAgIEl0ZXJhdG9yLml0ZXJhdGUobmV3IENJUygyTCwgKCkgPT4gb2RkUHJtcygpKSkKICAgICAgICAgICAgICAgICAgICAgeyhjaXM6IENJU1tMb25nXSkgPT4gY2lzLmNvbnQoKX0KICAgICAgLm1hcCB7KGNpczogQ0lTW0xvbmddKSA9PiBjaXMudn0KICB9CgogIHByaW50KHByaW1lcygpLmRyb3AoOTk5OTkpLm5leHQoKSkKfQovLyAwLjM2IHNlY29uZHMgYW5kIDMyMksgZm9yIDEwMAovLyAwLjQxIHNlY29uZHMgYW5kIDMyMksgZm9yIDEwMDAwCi8vIDEuMjkgc2Vjb25kcyBhbmQgMzIySyBmb3IgMTAwMDAwCi8vIDEyLjM3IHNlY29uZHMgYW5kIDMyMksgZm9yIDYwMDAwMCBmb3IgcGVyZm9ybWFuY2Ugb2YgYWJvdXQgMS40Mw==