// from http://stackoverflow.com/questions/20985539/scala-erastothenes-is-there-a-straightforward-way-to-replace-a-stream-with-an/20991776
def primes
(): Iterator
[Long
] = { // generic class as a Co Inductive Stream element
def mltpls
(p
: Long
): CIS
[Long
] = { 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 pairs
(mltplss
: CIS
[CIS
[Long
]]): CIS
[CIS
[Long
]] = { new CIS
(merge
(mltplss.
v, tl.
v),
() => pairs
(tl.
cont())) }
def mrgMltpls
(mlps
: CIS
[CIS
[Long
]]): CIS
[Long
] = new CIS
(mlps.
v.
v,
() => merge
(mlps.
v.
cont(), mrgMltpls
(pairs
(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.37 seconds and 322K for 100
// 0.45 seconds and 322K for 10000
// 0.76 seconds and 322K for 100000
// 5.13 seconds and 322K for 1000000 for performance of about 1.09
Ly8gZnJvbSBodHRwOi8vc3RhY2tvdmVyZmxvdy5jb20vcXVlc3Rpb25zLzIwOTg1NTM5L3NjYWxhLWVyYXN0b3RoZW5lcy1pcy10aGVyZS1hLXN0cmFpZ2h0Zm9yd2FyZC13YXktdG8tcmVwbGFjZS1hLXN0cmVhbS13aXRoLWFuLzIwOTkxNzc2CgpvYmplY3QgTWFpbiBleHRlbmRzIEFwcCB7CiAgZGVmIHByaW1lcygpOiBJdGVyYXRvcltMb25nXSA9IHsKICAgIC8vIGdlbmVyaWMgY2xhc3MgYXMgYSBDbyBJbmR1Y3RpdmUgU3RyZWFtIGVsZW1lbnQKICAgIGNsYXNzIENJU1tBXSh2YWwgdjogQSwgdmFsIGNvbnQ6ICgpID0+IENJU1tBXSkKCiAgICBkZWYgbWx0cGxzKHA6IExvbmcpOiBDSVNbTG9uZ10gPSB7CiAgICAgIHZhciBweDIgPSBwICogMgogICAgICBkZWYgbnh0bWx0cGwoY21wc3Q6IExvbmcpOiBDSVNbTG9uZ10gPQogICAgICAgIG5ldyBDSVMoY21wc3QsICgpID0+IG54dG1sdHBsKGNtcHN0ICsgcHgyKSkKICAgICAgbnh0bWx0cGwocCAqIHApCiAgICB9CiAgICBkZWYgYWxsTWx0cGxzKG1wczogQ0lTW0xvbmddKTogQ0lTW0NJU1tMb25nXV0gPQogICAgICBuZXcgQ0lTKG1sdHBscyhtcHMudiksICgpID0+IGFsbE1sdHBscyhtcHMuY29udCgpKSkKICAgIGRlZiBtZXJnZShhOiBDSVNbTG9uZ10sIGI6IENJU1tMb25nXSk6IENJU1tMb25nXSA9CiAgICAgIGlmIChhLnYgPCBiLnYpIG5ldyBDSVMoYS52LCAoKSA9PiBtZXJnZShhLmNvbnQoKSwgYikpCiAgICAgIGVsc2UgaWYgKGEudiA+IGIudikgbmV3IENJUyhiLnYsICgpID0+IG1lcmdlKGEsIGIuY29udCgpKSkKICAgICAgZWxzZSBuZXcgQ0lTKGIudiwgKCkgPT4gbWVyZ2UoYS5jb250KCksIGIuY29udCgpKSkKICAgIGRlZiBwYWlycyhtbHRwbHNzOiBDSVNbQ0lTW0xvbmddXSk6IENJU1tDSVNbTG9uZ11dID0gewogICAgICB2YWwgdGwgPSBtbHRwbHNzLmNvbnQoKQogICAgICBuZXcgQ0lTKG1lcmdlKG1sdHBsc3MudiwgdGwudiksICgpID0+IHBhaXJzKHRsLmNvbnQoKSkpCiAgICB9CiAgICBkZWYgbXJnTWx0cGxzKG1scHM6IENJU1tDSVNbTG9uZ11dKTogQ0lTW0xvbmddID0KICAgICAgbmV3IENJUyhtbHBzLnYudiwgKCkgPT4gbWVyZ2UobWxwcy52LmNvbnQoKSwgbXJnTWx0cGxzKHBhaXJzKG1scHMuY29udCgpKSkpKQogICAgZGVmIG1pbnVzU3RydEF0KG46IExvbmcsIGNtcHN0czogQ0lTW0xvbmddKTogQ0lTW0xvbmddID0KICAgICAgaWYgKG4gPCBjbXBzdHMudikgbmV3IENJUyhuLCAoKSA9PiBtaW51c1N0cnRBdChuICsgMiwgY21wc3RzKSkKICAgICAgZWxzZSBtaW51c1N0cnRBdChuICsgMiwgY21wc3RzLmNvbnQoKSkKICAgIC8vIHRoZSBmb2xsb3dpbmcgYXJlIHJlY3Vyc2l2ZSwgd2hlcmUgY21wc3RzIHVzZXMgb2RkUHJtcyBhbmQKICAgIC8vIG9kZFBybXMgdXNlcyBhIGRlbGF5ZWQgdmVyc2lvbiBvZiBjbXBzdHMgaW4gb3JkZXIgdG8gYXZvaWQgYSByYWNlCiAgICAvLyBhcyBvZGRQcm1zIHdpbGwgYWxyZWFkeSBoYXZlIGEgZmlyc3QgdmFsdWUgd2hlbiBjbXBzdHMgaXMgY2FsbGVkIHRvIGdlbmVyYXRlIHRoZSBzZWNvbmQKICAgIGRlZiBjbXBzdHMoKTogQ0lTW0xvbmddID0gbXJnTWx0cGxzKGFsbE1sdHBscyhvZGRQcm1zKCkpKQogICAgZGVmIG9kZFBybXMoKTogQ0lTW0xvbmddID0gbmV3IENJUygzLCAoKSA9PiBtaW51c1N0cnRBdCg1TCwgY21wc3RzKCkpKQogICAgSXRlcmF0b3IuaXRlcmF0ZShuZXcgQ0lTKDJMLCAoKSA9PiBvZGRQcm1zKCkpKQogICAgICAgICAgICAgICAgICAgICB7KGNpczogQ0lTW0xvbmddKSA9PiBjaXMuY29udCgpfQogICAgICAubWFwIHsoY2lzOiBDSVNbTG9uZ10pID0+IGNpcy52fQogIH0KCiAgcHJpbnQocHJpbWVzKCkuZHJvcCg5OTk5OSkubmV4dCgpKQp9Ci8vIDAuMzcgc2Vjb25kcyBhbmQgMzIySyBmb3IgMTAwCi8vIDAuNDUgc2Vjb25kcyBhbmQgMzIySyBmb3IgMTAwMDAKLy8gMC43NiBzZWNvbmRzIGFuZCAzMjJLIGZvciAxMDAwMDAKLy8gNS4xMyBzZWNvbmRzIGFuZCAzMjJLIGZvciAxMDAwMDAwIGZvciBwZXJmb3JtYW5jZSBvZiBhYm91dCAxLjA5