public
Created

Prime range using a prieme sieve

  • Download Gist
main.d
D
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
import std.stdio, std.algorithm, std.array, std.range, std.conv;
 
auto nextPrime(I)(I n)
{
static auto isPrime(I n)
{
for(I i = 2; i * i <= n; i++)
if(n % i == 0)
return false;
return true;
}
 
do { n++; } while(!isPrime(n));
return n;
}
 
struct Primes(I)
{
I[] smallPrimes;
I start;
I offset;
bool[] isPrime;
@property auto front()
{
return start + offset;
}
 
void popFront()
{
do
{
offset ++;
 
if(offset == isPrime.length)
{
offset = 0;
start += isPrime.length;
 
if(smallPrimes.back ^^ 2 < start + isPrime.length)
{
smallPrimes ~= nextPrime(smallPrimes.back);
isPrime.length = isPrime.length + 1;
}
 
isPrime []= true;
 
foreach(p; smallPrimes)
{
auto multiple = (start / p) * p;
if(multiple != start)
multiple += p;
for(;multiple -start < isPrime.length; multiple += p)
isPrime[multiple - start] = false;
}
}
} while(!isPrime[offset]);
}
 
enum empty = false;
}
 
auto primes(I = int)()
{
return Primes!I([to!I(2)], to!I(2), to!I(0), [true]);
}
 
void main()
{
writeln(drop(primes(), 999999).front);
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.