// 2004-02-07 Chris Hodapp

#include <stdio.h>

int main() {
    unsigned long max, i, j, i2, step;
    char *sieve;

    printf("Maximum prime? ");
    scanf("%li", &max);
    sieve = (char *) malloc((max+1) * sizeof(char));

    sieve[2] = 0;
    for(i = 4; i < max; i += 2) {
        sieve[i] = 1;
        sieve[i-1] = 0;
    }

    for(i = 3; i*i <= max; ++i) {
        if (sieve[i]) continue;
        for(j = i*i; j <= max; j += 2*i) sieve[j] = 1;
    }

    for(i = 2; i < max; ++i) if (!(sieve[i])) printf("%li\n", i);
}