#define _GNU_SOURCE             // so we get LONG_LONG_MAX
#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

enum { true = 1, false = 0 };

int
main(int argc, char **argv)
{
  assert(LONG_LONG_MAX > INT_MAX);
  int nn;
  int work_done = 0;
  if (argc != 2 || !(nn = atoi(argv[1]))) {
    fprintf(stderr, "Usage: %s n\n", argv[0]);
    return 1;
  }

  char *is_composite = malloc(nn);
  if (!is_composite) {
    perror("malloc");
    return 1;
  }

  for (int ii = 0; ii < nn; ii++) is_composite[ii] = false;
  work_done += nn;
  printf("2\n");

  for (int ii = 3; ii < nn; ii += 2) {
    if (!is_composite[ii]) {
      printf("%d\n", ii);
      work_done++;
    }

    /* Curse C for not having a way to detect overflow, but RIP DMR */
    if (ii * (long long)ii > INT_MAX) continue;

    for (int jj = ii*ii; jj < nn; jj += ii) {
      is_composite[jj] = true;
      work_done++;
    }
  }

  fprintf(stderr, "Did %d steps of work.\n", work_done);
  
  return 0;
}