#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;
}