## digitalmars.D.learn - Erastothenes

- Dave Colling <djcolling tiscali.co.uk> Jun 14 2007
- davidb <ta-nospam-zz gmx.at> Jun 14 2007
- Chris Nicholson-Sauls <ibisbasenji gmail.com> Jun 14 2007
- "Stewart Gordon" <smjg_1998 yahoo.com> Jun 14 2007
- davidb <ta-nospam-zz gmx.at> Jun 14 2007

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

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

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

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

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

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

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

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