www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Erastothenes

reply Dave Colling <djcolling tiscali.co.uk> writes:
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!
Jun 14 2007
parent reply davidb <ta-nospam-zz gmx.at> writes:
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


/* Eratosthenes Sieve prime number calculation. */

module sieve;
import std.stdio;

void main()
{
     writefln("finding prime numbers with: 2 <= prime <= 8191");
     int count;
     bool flags[8192] = true;    // find primes with: 2 <= prime <= 8191
     flags[0] = flags[1] = false;
     for (int i = 2; i < flags.length; i++)
     {
         if (flags[i])           // we have a prime
         {	
             writef(i, " ");
             count += 1;
             int k = i*i;
             // now delete all multiples of the prime
             while (k < flags.length)
             {
                 flags[k] = false;
                 k += i;
             }
         }
     }
     writefln("\nfound %d primes", count);
}
Jun 14 2007
next sibling parent Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
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.


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
Jun 14 2007
prev sibling parent reply "Stewart Gordon" <smjg_1998 yahoo.com> writes:
"davidb" <ta-nospam-zz gmx.at> wrote in message 
news:f4rvk2$1u7k$1 digitalmars.com...

 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)


It does work.  You appear to have not seen the line

    prime = i + i + 3;

I added this line

    writefln("i = %d; prime = %d", i, prime);

at the end of the if block to see what's happening.

But there are a few flaws with it.  It sets a bad example not only by using 
printf, but also by being badly commented and by declaring everything in one 
place.  And by using 1 and 0 instead of true and false.

But 3 to 16383 seems a peculiar range to count.  If only it added 1 to the 
count, it would give the number of primes below 1 << 14, which seems more 
what one would expect.

And if multiple iterations are meant to be for benchmarking, 10 is nowhere 
near enough on modern systems.

Stewart.
Jun 14 2007
parent davidb <ta-nospam-zz gmx.at> writes:
Stewart Gordon wrote:

 
 "davidb" <ta-nospam-zz gmx.at> wrote in message 
 news:f4rvk2$1u7k$1 digitalmars.com...

 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)


 
 It does work.  You appear to have not seen the line
 
    prime = i + i + 3;
 
 I added this line
 
    writefln("i = %d; prime = %d", i, prime);
 
 at the end of the if block to see what's happening.
 
 But there are a few flaws with it.  It sets a bad example not only by 
 using printf, but also by being badly commented and by declaring 
 everything in one place.  And by using 1 and 0 instead of true and false.
 
 But 3 to 16383 seems a peculiar range to count.  If only it added 1 to 
 the count, it would give the number of primes below 1 << 14, which seems 
 more what one would expect.
 
 And if multiple iterations are meant to be for benchmarking, 10 is 
 nowhere near enough on modern systems.
 
 Stewart.


Yes, I wrote too fast. But what I did was to check flags[],
which indicates all these numbers as primes...
(which would be the intuitive result at least to me
and is the usual approach as far as I have sieve's encountered so far).


David
Jun 14 2007