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

#define BIT(x) (1 << (x))

int main(int argc, char* argv[]) {
  size_t n, l, i, j; uint8_t* primes;
  if (argc != 2 || (n = strtoul(argv[1], NULL, 10)) < 2) {
    fprintf(stderr, "using: %s (num >= 2)\n", argv[0]);
    return 1;
  }
  l = (size_t)sqrt(n) | 1;
  if ((primes = malloc(n / 8 + 1)) == NULL) {
    fprintf(stderr, "malloc() failed -- number too big?\n");
    return 1;
  }
  memset(primes, 0xAA, n / 8 + 1);
  printf("2\n");
  for (i = 3; i <= l; i += 2) {
    if (primes[i / 8] & BIT(i % 8)) {
      for (j = i * i; j <= n; j += i) primes[j / 8] &= ~BIT(j % 8);
      printf("%zu\n", i);
    }
  }
  for (; i <= n; i += 2)
    if (primes[i / 8] & BIT(i % 8))
      printf("%zu\n", i);
}