/* The sieve of Eratosthenes - a program to store and print prime numbers */
enum { /* Use enum to define some constants */
MAX_PRIME= 101, /* Define the prime number which we will go up to */
CROSSED= 1, /* Use this to set an element of the sieve to be
crossed out */
UNCROSSED= 0 /* Use this to set an element of the sieve to be not
crossed out */
};
int find_next_k (int [MAX_PRIME]);
/* Finds and returns the next uncrossed prime on our table of primes */
void cross_k (int, int [MAX_PRIME]);
/* Crosses out all multiples of k except for k itself */
int main()
{
int sieve[MAX_PRIME]; /* An array to hold our sieve */
int k; /* Holds the current prime number we are crossing out*/
int i; /* Used for loops */
for (i= 0; i < MAX_PRIME; i++) {
sieve[i]= UNCROSSED;
}
sieve[0]= CROSSED; /* zero is not prime */
sieve[1]= CROSSED; /* one is not prime */
k= find_next_k(sieve); /* Find the next value of k which isn't crossed */
while (k < sqrt (MAX_PRIME)) { /* Check all prime numbers <= the
square root of the max prime we are looking for -
remember that the maximum prime will be 1 less
than MAX_PRIME due to arrays running from 0 */
cross_k(k, sieve); /* Cross out all multiples of k */
k= find_next_k(sieve); /* Find the next value of k */
}
/* Print out prime numbers */
for (i= 1; i < MAX_PRIME; i++) {
if (sieve[i] == CROSSED) {
printf ("%d is not prime.\n",i);
} else {
printf ("%d is prime.\n",i);
}
}
return 0;
}
int find_next_k (int sieve[MAX_PRIME])
/* Find the next uncrossed value of k */
{
static int k= 1; /* Use a static variable to store where we've got to
so far */
/* WRITE CODE HERE. YOUR CODE SHOULD:
1) include a while loop which checks k is less than MAX_PRIME
2) adds one to k
3) if sieve[k] is UNCROSSED then return k
4) if not then carry on round the loop */
}
void cross_k (int k, int sieve[MAX_PRIME])
/* Cross out all multiples of k except k itself */
{
/* WRITE CODE HERE. YOUR CODE SHOULD:
Use a for loop
Cross out every square which is a multiple of k except k itself
i.e we want to cross out 2k, 3k, 4k, 5k etc
It should not try to set any square in the sieve beyond MAX_PRIME*/
}