Eratosthenes' Sieve (idea)

This implementation takes the smallest known prime that hasn't yet been sieved "currprime" and removes all multiples less than PRIME_MAX from the array. Once the square of currprime is greater than or equal to PRIME_MAX, it stops. As noted above, we can start with the square of currprime, since all lesser multiples will have already been removed.

The program uses an array of chars to hold the primeness of each number from 0 to PRIME_MAX - 1. Each char holds 1 if the index is a prime, or zero otherwise. Since only a bit of storage is needed, storing the primeness in a char is wasteful, but simplifies the code considerably.

#include <stdio.h>

#define PRIME_MAX 100

char sieve[PRIME_MAX];

int nextPrime(int lastprime) {
    int i;

    for (i = lastprime + 1; i < PRIME_MAX; i++)
        if (sieve[i] == 1)
            return i;

    return 0;
}

int main() {
    int i, currprime;

    sieve[0] = 0;
    sieve[1] = 0;
    for (i = 2; i < PRIME_MAX; i++)
        sieve[i] = 1;

    currprime = nextPrime(0);
    while ((currprime * currprime) < PRIME_MAX) {

        for (i = (currprime * currprime); i < PRIME_MAX; i += currprime)
            sieve[i] = 0;

        currprime = nextPrime(currprime);
    }

    for (i = 0; i < PRIME_MAX; i++)
        if (sieve[i] == 1)
            printf("%d\n", i);

    return 0;
}