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

int main(int argc, char const *argv[]) {
    if (argc != 2) {
        printf("Usage: sieve N, where N is the desired maximum value for the sieve.\n");
        return -1;
    }

    int N = (unsigned long long) strtoull(argv[1], NULL, 10);

    // Stop sieve at sqrt of max # in sieve, because all non-primes are 
    // already gone.
    int M = (int) sqrt((double) N);

    if (N < 0) {
        printf("N must be positive.\n");
        return -1;
    }
    if (N < 2) {
        printf("No primes.\n");
        return 0;
    }

    int * primes;
    primes = calloc(N, sizeof(int));

    // 0 is untouched, 1 is not prime
    printf("2\n");
    for (int i = 3; i <= M; i=i+2) {
        if (primes[i] == 1) continue;
        printf("%d\n", i);
        for (int j = i * i; j <= N; j=j+i) {
            if (primes[j] == 1) continue;
                primes[j] = 1;
        }
    }
    if (!(M % 2)) M = M + 1;
    for (int i = M; i <= N; i=i+2) {
        if (primes[i] == 0) {
            printf("%d\n", i);
        }
    }

    return 0;
}