443,730 Members | 1,659 Online Need help? Post your question and get tips & solutions from a community of 443,730 IT Pros & Developers. It's quick & easy.

# Beginners prime number generator

 P: n/a Hi All; 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 #include #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; } do { for ( count = prime * 2 ; count <= MAXCOUNT; count = count + prime ) { search_array[count] = 0; } counter = prime + 1; nextprime = 0; stop = 0; do { if ( search_array[counter] != 0 ) { nextprime = search_array[counter]; stop = 0; } else { counter++; if ( pow(counter, 2) MAXCOUNT ) { stop = 1; } } } while( counter < MAXCOUNT && nextprime == 0); prime = nextprime; if (prime != 0) { printf("%d ", prime); } } while( stop == 0 ); return 0; } Dec 5 '06 #1
10 Replies

 P: n/a Joel Mayes wrote: Hi All; int search_array[MAXCOUNT]; /* Initialize the searching array from 1 -MAXCOUNT */ for ( count = 2; count <= MAXCOUNT; count++ ) { search_array[ count ] = count; } search_array contains MAXCOUNT ints. The first element is search_array, the last search_array[MAXCOUNT-1], so your code produces undefined behaviour when count equals MAXCOUNT. In best case scenario, it will coredump. The for loop should be: for (count=0; count < MAXCOUNT; count++) -- WYCIWYG - what you C is what you get Dec 5 '06 #2

 P: n/a 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 #include #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/ Dec 5 '06 #3

 P: n/a On 6 äÅË., 01:13, Joel Mayes #include #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; } do { for ( count = prime * 2 ; count <= MAXCOUNT; count = count + prime ) { search_array[count] = 0; } counter = prime + 1; nextprime = 0; stop = 0; do { if ( search_array[counter] != 0 ) { nextprime = search_array[counter]; stop = 0; } else { counter++; if ( pow(counter, 2) MAXCOUNT ) { stop = 1; } } } while( counter < MAXCOUNT && nextprime == 0); prime = nextprime; if (prime != 0) { printf("%d ", prime); } } while( stop == 0 ); return 0; }- óËÒÙÔØ ÃÉÔÉÒÕÅÍÙÊ ÔÅËÓÔ -- ðÏËÁÚÁÔØ ÃÉÔÉÒÕÅÍÙÊ ÔÅËÓÔ - http://magegame.ru/?rf=626f6764616e Dec 6 '06 #4

 P: n/a On 2006-12-05, we******@gmail.com I'm teaching myself C, and have written a prime number generator. Itis a pretty inefficient implementation of the Sieve of Eratosthenesto calculate primes up to 1,000,000. If anyone has time to critic andoffer my some feedback I'd be gratefulThanksJoel > 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. Thanks! (To matevzb too.) That outer do...while loop and the stop variables was to catch an infinite loop when the search for the next prime exited with nextprime = 0. Your method is much better! time tells my it finds all the primes upto 1,000,000 in half the time as the previous version Thanks again Joel /* Prime number calculator */ #include #include int main(int argc, char *argv[] ) { int count; int counter = 0; int prime = 3; /* Initialise prime first odd prime number we sieve * the even numbers before the main loop which allows * for faster iteration */ int nextprime = 0; int maxcount = atoi(argv) + 1; /* +1 to include to integer * entered not very efficient as I * still include zero and one in * the search_array, but easier to * visualise :-) */ int search_array[maxcount]; int maxsieve = sqrt(maxcount); for ( count = 0; count < maxcount; count++ ) { search_array[ count ] = 1; } for ( count = 4 ; count < maxcount; count += 2 ) { search_array[count] = 0; } do { for ( count = prime * prime ; count < maxcount; count = count + ( prime * 2 )) { search_array[count] = 0; } counter = prime + 1; nextprime = 0; do { if ( search_array[counter] != 0 ) { nextprime = counter; } else { counter++; } } while( counter <= maxsieve && nextprime == 0); prime = nextprime; } while( counter <= maxsieve ); for (count = 2; count < maxcount; count++) { if (search_array[count] != 0 ) printf("%d ", count); } printf("\n"); return 0; } Dec 6 '06 #5

 P: n/a Joel Mayes #include #include int main(int N,char **P) { enum {MAXCOUNT = 1000000}; typedef long long integer; #define integerf "%lld" static integer prime[MAXCOUNT],modulus[MAXCOUNT]; // static to avoid blowing out the stack // on a multi-megabyte stack frame. int n; integer k; for (n=0,k=2; n

 P: n/a Here's my effort: #include #define LIMIT 1000 int main(void) { int sieve[LIMIT+1] , i , j ; for (i=2 ; i<=LIMIT ; i++) sieve[i]=1 ; for (i=2 ; i <= LIMIT/2 ; i++) { if (!sieve[i]) continue ; for (j=i ; i*j <= LIMIT ; j++) { sieve[i*j] = 0 ; } } for (i=2 ; i<=LIMIT ; i++) { if (sieve[i]) printf("%d\n",i) ; } return 0 ; } Dec 6 '06 #7

 P: n/a On 2006-12-06, SM Ryan wrote: Joel Mayes 'cause I don't know enough C to grok your code :-) Give me a couple of hours to read it through... Thanks Joel Dec 7 '06 #8

 P: n/a On 2006-12-06, Spiros Bousbouras Thanks, that much more elegant then mine, its a good learning experience to read different code that does the same thing Cheers Joel Dec 7 '06 #9

 P: n/a Joel Mayes # Why not the first million primes? # # # # 'cause I don't know enough C to grok your code :-) # # Give me a couple of hours to read it through... The test for primality of N is whether for no prime P

 P: n/a On 2006-12-07, SM Ryan wrote: Joel Mayes # Why not the first million primes? # # # # 'cause I don't know enough C to grok your code :-) # # Give me a couple of hours to read it through... Thanks, just back from a quick trip to the beach, I'll have a good study of this later today. Cheers Joel Dec 14 '06 #11

### This discussion thread is closed

Replies have been disabled for this discussion. 