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/