Erastothenes

[Chris Nicholson-Sauls]

davidb wrote:
> Dave Colling wrote:
>> Has anyone confirmed that the example showing how to find primes
>> by the sieve of Erastothenes actuall works?
>> It certainly counts something, but they are not primes!
> 
> You're right, definitely not (includes 0, 1, 4, 8, 10, 14, 20, 22, 25, ...)
> It still features printf instead of writef and is in my opinion
> rather confusing for someone starting to learn by example.
> So here's a cleaned up version, placed in the public domain (hint)
> 
> David
> 
[... code snipped ...]

And here's one I wrote a little while back just to play around with, 
using Tango.  Its bound to be sub-optimal, as it was just a toy.  An 
experiment on the efficiency of associative-arrays.  With a limit of 
1,000,000 it clocks at a consistant 0.87s for me on a 2GHz Athlon.  At 
10,000,000 it jumps to ~25s or so.  Cough.

You can run it with 'eratos ### report' to confirm the results.  And, 
yes, it is public domain for whatever it may be worth.

<code>
module eratos ;

import tango .io         .Stdout    ;
import tango .util .time .StopWatch ;

static import Integer = tango .text .convert .Integer ;

ulong[] sieve (ulong max) {
   ulong[]     result = [2_UL] ;
   bool[ulong] list            ;

   for (
     ulong step = 3_UL;
     step <= max;
     step += 2
   ) {
     if (step in list) {
       list.remove(step);
     }
     else {
       result ~= step;
       for (
         ulong number = step * step;
         number <= max;
         number += step
       ) {
         if (number % 2) {
           list[number] = false;
         }
       }
     }
   }

   return result;
}

char[] prettyNumber (ulong number) {
   char[] tmp    ,
          result ;
   size_t i      ,
          j      ;

   while (number > 0) {
     j = cast(size_t) (number % 10);
     tmp ~= "0123456789"[j];
     number /= 10;
   }
   for (i = 0, j = 3; i < tmp.length; i += 3, j += 3) {
     if (j >= tmp.length) {
       result ~= tmp[i .. $];
     }
     else {
       result ~= tmp[i .. j] ~ ',';
     }
   }
   result.reverse;
   return result;
}

const DEFAULT_LIMIT = 10_000_UL ;

void main (char[][] args) {
   ulong     limit  = DEFAULT_LIMIT ;
   ulong[]   primes                 ;
   Interval  elapse                 ;
   StopWatch timer                  ;

   if (args.length > 1) {
     limit = Integer.convert(args[1]);
   }

   timer.start;
   primes = sieve(limit);
   elapse = timer.stop;
   Stdout.formatln(
     "{} primes thru {} computed in {} seconds.",
     prettyNumber(primes.length), prettyNumber(limit), elapse).flush;
   if (args.length > 2) {
     foreach (index, value; primes) {
       Stdout.formatln("    [{,3:u}] {:u}", index, value).flush;
     }
   }
}
</code>

-- Chris Nicholson-Sauls