A simple sieve in Phobos?

[Chris Williams]

On Wednesday, 19 March 2014 at 18:40:49 UTC, Chris Williams wrote:
> 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;
> }

Well bummer, my quick and easy optimization broke the result for 
some reason. Here's a version that actually produces the correct 
answers, while I try and debug:

enum uint MAX_N = 10_000_000U;

void calcPrimes() {
     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;
             for (uint L2 = 0; L2 < list.length; L2++) {
                 uint val = list[L2];
                 markers[ L + val ] ~= val;
             }
         }
     }
}

void main() {
     calcPrimes;
}