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!

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

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

"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. 

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