fork download
copy 
  1. /// Prime sieve based on: http://w...content-available-to-author-only...c.edu/~oneill/papers/Sieve-JFP.pdf
  2.  
  3. import std.container: Array, BinaryHeap, RedBlackTree;
  4.  
  5. struct LazyPrimeSieve {
  6.     @property bool empty() const pure nothrow @safe @nogc {
  7.         return i > 203_280_221; // Pi(2 ^^ 32).
  8.     }
  9.  
  10.     @property auto front() const pure nothrow @safe @nogc {
  11.         return prime;
  12.     }
  13.  
  14.     @property void popFront() pure nothrow /*@safe*/ {
  15.         prime = sieveOne();
  16.     }
  17.  
  18. private:
  19.     static struct Wheel2357 {
  20.         static immutable ubyte[48] holes = [2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6,
  21.             2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6,
  22.             4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10];
  23.         static immutable ubyte[4] spokes = [2, 3, 5, 7];
  24.         static immutable ubyte first = 11;
  25.         uint i;
  26.  
  27.         auto spin() pure nothrow @safe @nogc {
  28.             return holes[i++ % $];
  29.         }
  30.     }
  31.  
  32.     static struct CompositeIterator {
  33.         uint prime;
  34.         Wheel2357 wheel;
  35.         ulong composite;
  36.  
  37.         this(uint p) pure nothrow @safe @nogc {
  38.             prime = p;
  39.             composite = p * wheel.first;
  40.         }
  41.  
  42.         void next() pure nothrow @safe @nogc {
  43.             composite += prime * wheel.spin;
  44.         }
  45.     }
  46.  
  47.     version (heap)  // Less memory but slower.
  48.         BinaryHeap!(Array!CompositeIterator, "a.composite > b.composite") iterators;
  49.     else            // Faster but is more GC intensive.
  50.         RedBlackTree!(CompositeIterator, "a.composite < b.composite", true) iterators;
  51.  
  52.     uint prime = 2;
  53.     uint i = 1;
  54.     Wheel2357 wheel;
  55.     uint candidate = wheel.first;
  56.  
  57.     uint sieveOne() pure nothrow /*@safe*/ {
  58.         switch (i) {
  59.             case 0: .. case wheel.spokes.length - 1:
  60.                 return wheel.spokes[i++];
  61.  
  62.             case wheel.spokes.length:
  63.                 i++;
  64.                 return candidate;
  65.  
  66.             case wheel.spokes.length + 1:
  67.                 version (heap) {}
  68.                 else
  69.                     iterators = new typeof(iterators);
  70.                 goto default;
  71.  
  72.             default:
  73.                 goto POST_RETURN;
  74.  
  75.                 while (true) {
  76.                     candidate += wheel.spin;
  77.  
  78.                     while (iterators.front.composite < candidate) {
  79.                         auto it = iterators.front;
  80.                         iterators.removeFront;
  81.                         it.next;
  82.                         iterators.insert(it);
  83.                     }
  84.  
  85.                     if (iterators.front.composite != candidate) {
  86.                         i++;
  87.                         return candidate;
  88.         POST_RETURN:
  89.                         // Only insert primes that are multiply
  90.                         // occuring in [0, 2 ^^ 32).
  91.                         if (candidate < 2 ^^ 16)
  92.                             iterators.insert(CompositeIterator(candidate));
  93.                     }
  94.                 }
  95.         }
  96.     }
  97. }
  98.  
  99.  
  100. void main() /*@safe*/ {
  101.     import std.stdio, std.algorithm, std.range;
  102.  
  103.     writeln("1,000,000th prime: ", LazyPrimeSieve().dropExactly(1000000-1).front);
  104. }
Success #stdin #stdout 1.9s 17376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1,000,000th prime: 15485863
https://ideone.com/n5EfqI
language:
D (dmd 2.085.0)
created:
7 years ago
visibility:
public

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!