/// Prime sieve based on: http://w...content-available-to-author-only...c.edu/~oneill/papers/Sieve-JFP.pdf
import std.container: Array, BinaryHeap, RedBlackTree;
struct LazyPrimeSieve {
@property bool empty() const pure nothrow @safe @nogc {
return i > 203_280_221; // Pi(2 ^^ 32).
}
@property auto front() const pure nothrow @safe @nogc {
return prime;
}
@property void popFront() pure nothrow /*@safe*/ {
prime = sieveOne();
}
private:
static struct Wheel2357 {
static immutable ubyte[48] holes = [2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6,
2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6,
4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10];
static immutable ubyte[4] spokes = [2, 3, 5, 7];
static immutable ubyte first = 11;
uint i;
auto spin() pure nothrow @safe @nogc {
return holes[i++ % $];
}
}
static struct CompositeIterator {
uint prime;
Wheel2357 wheel;
ulong composite;
this(uint p) pure nothrow @safe @nogc {
prime = p;
composite = p * wheel.first;
}
void next() pure nothrow @safe @nogc {
composite += prime * wheel.spin;
}
}
version (heap) // Less memory but slower.
BinaryHeap!(Array!CompositeIterator, "a.composite > b.composite") iterators;
else // Faster but is more GC intensive.
RedBlackTree!(CompositeIterator, "a.composite < b.composite", true) iterators;
uint prime = 2;
uint i = 1;
Wheel2357 wheel;
uint candidate = wheel.first;
uint sieveOne() pure nothrow /*@safe*/ {
switch (i) {
case 0: .. case wheel.spokes.length - 1:
return wheel.spokes[i++];
case wheel.spokes.length:
i++;
return candidate;
case wheel.spokes.length + 1:
version (heap) {}
else
iterators = new typeof(iterators);
goto default;
default:
goto POST_RETURN;
while (true) {
candidate += wheel.spin;
while (iterators.front.composite < candidate) {
auto it = iterators.front;
iterators.removeFront;
it.next;
iterators.insert(it);
}
if (iterators.front.composite != candidate) {
i++;
return candidate;
POST_RETURN:
// Only insert primes that are multiply
// occuring in [0, 2 ^^ 32).
if (candidate < 2 ^^ 16)
iterators.insert(CompositeIterator(candidate));
}
}
}
}
}
void main() /*@safe*/ {
import std.stdio, std.algorithm, std.range;
writeln("1,000,000th prime: ", LazyPrimeSieve().dropExactly(1000000-1).front);
}
Ly8vIFByaW1lIHNpZXZlIGJhc2VkIG9uOiBodHRwOi8vdy4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uYy5lZHUvfm9uZWlsbC9wYXBlcnMvU2lldmUtSkZQLnBkZgogCmltcG9ydCBzdGQuY29udGFpbmVyOiBBcnJheSwgQmluYXJ5SGVhcCwgUmVkQmxhY2tUcmVlOwogCnN0cnVjdCBMYXp5UHJpbWVTaWV2ZSB7CiAgICBAcHJvcGVydHkgYm9vbCBlbXB0eSgpIGNvbnN0IHB1cmUgbm90aHJvdyBAc2FmZSBAbm9nYyB7CiAgICAgICAgcmV0dXJuIGkgPiAyMDNfMjgwXzIyMTsgLy8gUGkoMiBeXiAzMikuCiAgICB9CiAKICAgIEBwcm9wZXJ0eSBhdXRvIGZyb250KCkgY29uc3QgcHVyZSBub3Rocm93IEBzYWZlIEBub2djIHsKICAgICAgICByZXR1cm4gcHJpbWU7CiAgICB9CiAKICAgIEBwcm9wZXJ0eSB2b2lkIHBvcEZyb250KCkgcHVyZSBub3Rocm93IC8qQHNhZmUqLyB7CiAgICAgICAgcHJpbWUgPSBzaWV2ZU9uZSgpOwogICAgfQogCnByaXZhdGU6CiAgICBzdGF0aWMgc3RydWN0IFdoZWVsMjM1NyB7CiAgICAgICAgc3RhdGljIGltbXV0YWJsZSB1Ynl0ZVs0OF0gaG9sZXMgPSBbMiwgNCwgMiwgNCwgNiwgMiwgNiwgNCwgMiwgNCwgNiwgNiwKICAgICAgICAgICAgMiwgNiwgNCwgMiwgNiwgNCwgNiwgOCwgNCwgMiwgNCwgMiwgNCwgOCwgNiwgNCwgNiwgMiwgNCwgNiwgMiwgNiwgNiwKICAgICAgICAgICAgNCwgMiwgNCwgNiwgMiwgNiwgNCwgMiwgNCwgMiwgMTAsIDIsIDEwXTsKICAgICAgICBzdGF0aWMgaW1tdXRhYmxlIHVieXRlWzRdIHNwb2tlcyA9IFsyLCAzLCA1LCA3XTsKICAgICAgICBzdGF0aWMgaW1tdXRhYmxlIHVieXRlIGZpcnN0ID0gMTE7CiAgICAgICAgdWludCBpOwogCiAgICAgICAgYXV0byBzcGluKCkgcHVyZSBub3Rocm93IEBzYWZlIEBub2djIHsKICAgICAgICAgICAgcmV0dXJuIGhvbGVzW2krKyAlICRdOwogICAgICAgIH0KICAgIH0KIAogICAgc3RhdGljIHN0cnVjdCBDb21wb3NpdGVJdGVyYXRvciB7CiAgICAgICAgdWludCBwcmltZTsKICAgICAgICBXaGVlbDIzNTcgd2hlZWw7CiAgICAgICAgdWxvbmcgY29tcG9zaXRlOwogCiAgICAgICAgdGhpcyh1aW50IHApIHB1cmUgbm90aHJvdyBAc2FmZSBAbm9nYyB7CiAgICAgICAgICAgIHByaW1lID0gcDsKICAgICAgICAgICAgY29tcG9zaXRlID0gcCAqIHdoZWVsLmZpcnN0OwogICAgICAgIH0KIAogICAgICAgIHZvaWQgbmV4dCgpIHB1cmUgbm90aHJvdyBAc2FmZSBAbm9nYyB7CiAgICAgICAgICAgIGNvbXBvc2l0ZSArPSBwcmltZSAqIHdoZWVsLnNwaW47CiAgICAgICAgfQogICAgfQogCiAgICB2ZXJzaW9uIChoZWFwKSAgLy8gTGVzcyBtZW1vcnkgYnV0IHNsb3dlci4KICAgICAgICBCaW5hcnlIZWFwIShBcnJheSFDb21wb3NpdGVJdGVyYXRvciwgImEuY29tcG9zaXRlID4gYi5jb21wb3NpdGUiKSBpdGVyYXRvcnM7CiAgICBlbHNlICAgICAgICAgICAgLy8gRmFzdGVyIGJ1dCBpcyBtb3JlIEdDIGludGVuc2l2ZS4KICAgICAgICBSZWRCbGFja1RyZWUhKENvbXBvc2l0ZUl0ZXJhdG9yLCAiYS5jb21wb3NpdGUgPCBiLmNvbXBvc2l0ZSIsIHRydWUpIGl0ZXJhdG9yczsKIAogICAgdWludCBwcmltZSA9IDI7CiAgICB1aW50IGkgPSAxOwogICAgV2hlZWwyMzU3IHdoZWVsOwogICAgdWludCBjYW5kaWRhdGUgPSB3aGVlbC5maXJzdDsKIAogICAgdWludCBzaWV2ZU9uZSgpIHB1cmUgbm90aHJvdyAvKkBzYWZlKi8gewogICAgICAgIHN3aXRjaCAoaSkgewogICAgICAgICAgICBjYXNlIDA6IC4uIGNhc2Ugd2hlZWwuc3Bva2VzLmxlbmd0aCAtIDE6CiAgICAgICAgICAgICAgICByZXR1cm4gd2hlZWwuc3Bva2VzW2krK107CiAKICAgICAgICAgICAgY2FzZSB3aGVlbC5zcG9rZXMubGVuZ3RoOgogICAgICAgICAgICAgICAgaSsrOwogICAgICAgICAgICAgICAgcmV0dXJuIGNhbmRpZGF0ZTsKIAogICAgICAgICAgICBjYXNlIHdoZWVsLnNwb2tlcy5sZW5ndGggKyAxOgogICAgICAgICAgICAgICAgdmVyc2lvbiAoaGVhcCkge30KICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICBpdGVyYXRvcnMgPSBuZXcgdHlwZW9mKGl0ZXJhdG9ycyk7CiAgICAgICAgICAgICAgICBnb3RvIGRlZmF1bHQ7CiAKICAgICAgICAgICAgZGVmYXVsdDoKICAgICAgICAgICAgICAgIGdvdG8gUE9TVF9SRVRVUk47CiAKICAgICAgICAgICAgICAgIHdoaWxlICh0cnVlKSB7CiAgICAgICAgICAgICAgICAgICAgY2FuZGlkYXRlICs9IHdoZWVsLnNwaW47CiAKICAgICAgICAgICAgICAgICAgICB3aGlsZSAoaXRlcmF0b3JzLmZyb250LmNvbXBvc2l0ZSA8IGNhbmRpZGF0ZSkgewogICAgICAgICAgICAgICAgICAgICAgICBhdXRvIGl0ID0gaXRlcmF0b3JzLmZyb250OwogICAgICAgICAgICAgICAgICAgICAgICBpdGVyYXRvcnMucmVtb3ZlRnJvbnQ7CiAgICAgICAgICAgICAgICAgICAgICAgIGl0Lm5leHQ7CiAgICAgICAgICAgICAgICAgICAgICAgIGl0ZXJhdG9ycy5pbnNlcnQoaXQpOwogICAgICAgICAgICAgICAgICAgIH0KIAogICAgICAgICAgICAgICAgICAgIGlmIChpdGVyYXRvcnMuZnJvbnQuY29tcG9zaXRlICE9IGNhbmRpZGF0ZSkgewogICAgICAgICAgICAgICAgICAgICAgICBpKys7CiAgICAgICAgICAgICAgICAgICAgICAgIHJldHVybiBjYW5kaWRhdGU7CiAgICAgICAgUE9TVF9SRVRVUk46CiAgICAgICAgICAgICAgICAgICAgICAgIC8vIE9ubHkgaW5zZXJ0IHByaW1lcyB0aGF0IGFyZSBtdWx0aXBseQogICAgICAgICAgICAgICAgICAgICAgICAvLyBvY2N1cmluZyBpbiBbMCwgMiBeXiAzMikuCiAgICAgICAgICAgICAgICAgICAgICAgIGlmIChjYW5kaWRhdGUgPCAyIF5eIDE2KQogICAgICAgICAgICAgICAgICAgICAgICAgICAgaXRlcmF0b3JzLmluc2VydChDb21wb3NpdGVJdGVyYXRvcihjYW5kaWRhdGUpKTsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9CiAKIAp2b2lkIG1haW4oKSAvKkBzYWZlKi8gewogICAgaW1wb3J0IHN0ZC5zdGRpbywgc3RkLmFsZ29yaXRobSwgc3RkLnJhbmdlOwogCiAgICB3cml0ZWxuKCIxLDAwMCwwMDB0aCBwcmltZTogIiwgTGF6eVByaW1lU2lldmUoKS5kcm9wRXhhY3RseSgxMDAwMDAwLTEpLmZyb250KTsKfQ==