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