Skip to content

@jkrempus /main.d
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Prime range using a prieme sieve
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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.