// your code goes here // http://stackoverflow.com/q/20985539/849891,
def primes
( ) : Stream
[ Int
] = { // basis for mMaJOa def merge
( a
: Stream
[ Int
] , b
: Stream
[ Int
] ) : Stream
[ Int
] = { def next
= a.
head min b.
head Stream.
cons ( next, merge
( if ( a.
head == next
) a.
tail else a,
if ( b.
head == next
) b.
tail else b
) ) }
def test
( n
: Int, compositeStream
: Stream
[ Int
] ) : Stream
[ Int
] = { if ( n
== compositeStream.
head ) test
( n+
1 , compositeStream.
tail ) test( n+1 , merge( compositeStream, Stream.from ( n* n, n) ) ) )
}
test( 2 , Stream.from ( 4 , 2 ) )
}
// 2:0.39s-382M 100:0.41s-382M 200: 0.42s-382M zero-time=0.39s
print( primes( ) .drop ( 1100 ) .head )
// 500: 0.59s-382M 1000:1.97s-383M n^2.98
} // 1100:2.54s-384M n^3.23(vs 1000) n^3.0(vs 500)
b2JqZWN0IE1haW4gZXh0ZW5kcyBBcHAgeyAvLyAgY29kZSBieSBzdGV3U3F1YXJlZCAsIGZyb20KCS8vIHlvdXIgY29kZSBnb2VzIGhlcmUgIC8vICBodHRwOi8vc3RhY2tvdmVyZmxvdy5jb20vcS8yMDk4NTUzOS84NDk4OTEsCglkZWYgcHJpbWVzKCk6IFN0cmVhbVtJbnRdID0geyAgLy8gYmFzaXMgZm9yIG1NYUpPYQogICAgICBkZWYgbWVyZ2UoYTogU3RyZWFtW0ludF0sIGI6IFN0cmVhbVtJbnRdKTogU3RyZWFtW0ludF0gPSB7CiAgICAgICAgZGVmIG5leHQgPSBhLmhlYWQgbWluIGIuaGVhZAogICAgICAgIFN0cmVhbS5jb25zKG5leHQsIG1lcmdlKGlmIChhLmhlYWQgPT0gbmV4dCkgYS50YWlsIGVsc2UgYSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZiAoYi5oZWFkID09IG5leHQpIGIudGFpbCBlbHNlIGIpKQogICAgICB9CiAgICAgIGRlZiB0ZXN0KG46IEludCwgY29tcG9zaXRlU3RyZWFtOiBTdHJlYW1bSW50XSk6IFN0cmVhbVtJbnRdID0gewogICAgICAgIGlmIChuID09IGNvbXBvc2l0ZVN0cmVhbS5oZWFkKSB0ZXN0KG4rMSwgY29tcG9zaXRlU3RyZWFtLnRhaWwpCiAgICAgICAgZWxzZSBTdHJlYW0uY29ucyhuLCAKICAgICAgICAgICAgICAgdGVzdChuKzEsIG1lcmdlKGNvbXBvc2l0ZVN0cmVhbSwgU3RyZWFtLmZyb20obipuLCBuKSkpKQogICAgICB9CiAgICAgIHRlc3QoMiwgU3RyZWFtLmZyb20oNCwgMikpCiAgICB9CiAgICAgICAgIC8vIDI6MC4zOXMtMzgyTSAxMDA6MC40MXMtMzgyTSAgMjAwOiAwLjQycy0zODJNICB6ZXJvLXRpbWU9MC4zOXMKCXByaW50KHByaW1lcygpLmRyb3AoMTEwMCkuaGVhZCkgIAoJICAgICAvLyA1MDA6IDAuNTlzLTM4Mk0gIDEwMDA6MS45N3MtMzgzTSBuXjIuOTggIAp9ICAgICAgICAvLyAxMTAwOjIuNTRzLTM4NE0gbl4zLjIzKHZzIDEwMDApIG5eMy4wKHZzIDUwMCk=