A simple sieve in Phobos?
Chris Williams
yoreanon-chrisw at yahoo.co.jp
Wed Mar 19 11:40:48 PDT 2014
On Tuesday, 18 March 2014 at 14:23:32 UTC, bearophile wrote:
> There is a efficient Sieve implementation in C++ here:
>
> http://code.activestate.com/recipes/577966-even-faster-prime-generator/?in=lang-cpp
>
> There are of course far faster implementations, but its
> performance is not bad, while being still simple and quite
> short.
Here's a straightforward implementation, if you don't already
have one (I assume you're doing this for Rosetta Code). I had to
decrease your MAX_N by 100-fold to get a similar runtime, but
it's a fairly faithful implementation of Eratosthenes' method as
written.
enum uint MAX_N = 10_000_000U;
void calcPrimes() pure nothrow {
uint[][uint] markers;
for (uint L = 2; L < MAX_N; L++) {
uint[]* pList = (L in markers);
if (pList is null) {
markers[L + L] = [L];
}
else {
uint[] list = *pList;
size_t len = list.length - 1;
for (uint L2 = 0; L2 < len; L2++) {
uint val = list[L2];
markers[ L + val ] ~= val;
}
// reuse the current list for the last item to save
allocations
list[0] = list[len];
list.length = 1;
markers[ L + list[len] ] = list;
}
}
}
void main() {
calcPrimes;
}
More information about the Digitalmars-d
mailing list