Joel Mayes wrote:
I'm teaching myself C, and have written a prime number generator. It is
a pretty inefficient implementation of the Sieve of Eratosthenes to
calculate primes up to 1,000,000. If anyone has time to critic and offer
my some feedback I'd be grateful
Thanks
Joel
#include<stdio.h>
#include<math.h>
#define MAXCOUNT 1000000
int main(void) {
int search_array[MAXCOUNT];
int count;
int prime = 2; /* initialize prime as a prime */
int nextprime = 0;
int counter = 0;
int stop = 0;
/* Initialize the searching array from 1 -MAXCOUNT */
for ( count = 2; count <= MAXCOUNT; count++ ) {
search_array[ count ] = count;
}
This leads to a buffer overflow condition. As a rule of thumb in C (as
well as languages that use for(;;) or while() like loops with algebraic
conditions and which have 0-based arrays), the upper array constraint
is typically tested by being *less than* (<) the length of the array.
This matches the correct indexability and gives you a tiling properly
(the index value at the end is the first entry beyond the end, for
example.)
In the Sieve of Eratosthenes it is not necessary that you store the
value of the index at the index position. You could use a char base
type for the array, for example, and simply store the value 1 for those
values not yet crossed off.
do {
for ( count = prime * 2 ; count <= MAXCOUNT; count = count + prime ) {
search_array[count] = 0;
}
Technically the starting position is count = prime * prime, since all
lower factors will have been removed already (by induction).
Furthermore, if the prime is odd, the incrementor can be 2*prime (since
otherwise every other number would be even which should have been
eliminated of the very first time through this loop.)
counter = prime + 1;
nextprime = 0;
stop = 0;
do {
if ( search_array[counter] != 0 ) {
nextprime = search_array[counter];
Or more simply, nextprime = counter;
stop = 0;
}
else {
counter++;
if ( pow(counter, 2) MAXCOUNT ) {
This is a bit twisted. You can just say counter * counter instead of
pow(counter,2). You should also comment why this is correct. And the
condition can be >= not just >. If you wanted to, you could hoist out
a sqrt(MAXCOUNT) calculation in the outer loop and just compare counter
to that directly.
Note that the reason you can check counter*counter >= MAXCOUNT here is
the same reason why you should use that as the initial counter value in
the loop above.
stop = 1;
}
}
} while( counter < MAXCOUNT && nextprime == 0);
prime = nextprime;
if (prime != 0) {
printf("%d ", prime);
}
} while( stop == 0 );
This is a kind of bizarre way of using your inner loop in two different
modes. And it is hiding an unnecessary performance drop. You can
simply break out of the loop when counter * counter >= MAXCOUNT (since
the sieving is done at that point) and simply output the remaining
primes without the need to perform any further sieving.
return 0;
}
I didn't check if it compiled, but it otherwise looks ok.
--
Paul Hsieh
http://www.pobox.com/~qed/ http://bstring.sf.net/ 
