Re: A simple sieve in Phobos?

[Chris Williams]

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;
}