www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - sieve.d: Improved

reply Andrew Edwards <ridimz_at yahoo.dot.com> writes:
The implementation of sieve.d as presented at the bottom of the overview
page and in /dmd/src/d/example/sieve.d are inaccurate.

After making the following changes to the program:

bit[8191] flags; ==> bit[10] flags; // for testing only

between for loop and [printf ("\n%d primes", count);] insert:

   debug(print) {
     foreach(int ndx, bit val; flags) {
       if(flags[ndx]) {
         printf("%4d\t",ndx);
       }
     }
   }

the following inaccurate output were observed:

10 iterations
    0	   1	   2	   4	   5	   7	   8	
7 primes


New Implementation:
------sieve.d------
// Copyright (c) 2004 by Andrew Edwards
// I give up my rights and permit others to:
//      distribute
//      sell
//      give
//      modify
//      use
// I retain the right to be know as the author/owner

bit[8191] sieve;
void main()
{
   sieve[2..sieve.length] = true;
   int cnt;
   foreach(int ndx, bit val; sieve) {
     if(ndx == 0 || ndx == 1) continue;
     for(int j = ndx; j*ndx < sieve.length; j++)
       sieve[ndx*j] = false;
     if(val) count++;
   }
   printf("\n%d primes", cnt);
}

Correct Output: // tested with bit[10] sieve;
---------------
    2	   3	   5	   7	
4 primes

ciao Andrew
Jul 03 2004
next sibling parent Andrew Edwards <ridimz_at yahoo.dot.com> writes:
Andrew Edwards wrote:

 The implementation of sieve.d as presented at the bottom of the overview
 page and in /dmd/src/d/example/sieve.d are inaccurate.
Sorry! Make that: /dmd/samples/d/sieve.d
Jul 03 2004
prev sibling parent Andrew Edwards <ridimz_at yahoo.dot.com> writes:
Andrew Edwards wrote:
       sieve[ndx*j] = false;
     if(val) count++;
correction: if(val) cnt++;
   }
   printf("\n%d primes", cnt);
 }
Jul 03 2004