## digitalmars.D.learn - Erastothenes

• Dave Colling (3/3) Jun 14 2007 Has anyone confirmed that the example showing how to find primes
• davidb (32/35) Jun 14 2007 You're right, definitely not (includes 0, 1, 4, 8, 10, 14, 20, 22, 25, ....
• Chris Nicholson-Sauls (84/96) Jun 14 2007 [... code snipped ...]
• Stewart Gordon (16/25) Jun 14 2007 It does work. You appear to have not seen the line
• davidb (6/42) Jun 14 2007 Yes, I wrote too fast. But what I did was to check flags[],
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
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
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.

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
```
Jun 14 2007
"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;

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

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