Beginners prime number generator

[Joel Mayes]

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<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;
}

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;
}

 

[matevzb]

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[0], 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++)

 

[websnarf]

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.

 

[bogdan]

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<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;
}

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

 

[Joel Mayes]

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<stdio.h>
#include<math.h>

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; /* +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;
}

 

[SM Ryan]

#
# 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

Why not the first million primes?

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

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<MAXCOUNT; k++) {
bool composite = false; int i;
for (i=0; i<n; i++) {
modulus -= 1;
if (modulus==0) {modulus = prime; composite = true;}
}
if (!composite) {
prime[n] = modulus[n] = k;
n += 1;
printf("[%d]: " integerf "\n",n,k);
}
}
return 0;
}

 

[Spiros Bousbouras]

Here's my effort:

#include <stdio.h>
#define LIMIT 1000

int main(void) {
int sieve[LIMIT+1] , i , j ;

for (i=2 ; i<=LIMIT ; i++) sieve=1 ;

for (i=2 ; i <= LIMIT/2 ; i++) {
if (!sieve) continue ;
for (j=i ; i*j <= LIMIT ; j++) {
sieve[i*j] = 0 ;
}
}
for (i=2 ; i<=LIMIT ; i++) {
if (sieve) printf("%d\n",i) ;
}
return 0 ;
}

 

[Joel Mayes]

#
# 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

Why not the first million primes?

<SNIP>

'cause I don't know enough C to grok your code

Give me a couple of hours to read it through...

Thanks

Joel

 

[Joel Mayes]

Here's my effort:

<SNIP>

Thanks, that much more elegant then mine, its a good learning experience
to read different code that does the same thing

Cheers

Joel

 

[SM Ryan]

# On 2006-12-06, SM Ryan wrote:
# > #
# > # 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
# >
# > Why not the first million primes?
#
# <SNIP>
#
# '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<Q, P divides Q.
Or equivalently in C operators whether for no P, Q%P = 0.

However modulus and division are expensive operations. The original
sieve works on the realization that Q%P = 0 iff Q = n*P for some n.
So starting from n=2, if you mark ever Pth spot, you've marked every
spot that must be composite. As you discover and sieve additional
primes, the places Q that are unmarked by all lesser primes are those
that have Q%P /= 0 for all lesser primes.

The usual sieve code
for each prime P
for each candidate Q
is Q a multiple of P?
add the least noncomposite Q to P
What I do is
for each candidate Q
for each prime P
is Q a multiple of P?
if Q is not composite add to the set of primes

In either case you can find primes without division
(which is faster) and you even avoid addition and
subtraction in my code, just increment and decrement
during a linear array scan. Which means you can represent
the numbers with character strings far beyond
long long long long ints. My code has the further
advantage that you can keep the arrays as serial disk
files so that limits are the maximum string you can
read into memory and then maximum lengths of a serial file.

[257702]: 3614129
[257703]: 3614137
[257704]: 3614147
[257705]: 3614153
[257706]: 3614173
[257707]: 3614179
[257708]: 3614203
[257709]: 3614207
[257710]: 3614209
[257711]: 3614227

 

[Joel Mayes]

# On 2006-12-06, SM Ryan wrote:
# > #
# > # 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
# >
# > Why not the first million primes?
#
# <SNIP>
#
# 'cause I don't know enough C to grok your code
#
# Give me a couple of hours to read it through...

<Good description snipped>

Thanks, just back from a quick trip to the beach, I'll have a good study
of this later today.

Cheers

Joel