// Tabulate prime factors with the Sieve of Eratosthenes.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct entry {
  int n;
  struct entry *next;
};

void croak()
{
  fprintf(stderr, "Something is very wrong\n");
  abort();
}

enum { max = 1000*1000 };       // Initializes in 160ms compiled with -O
struct entry *prime_factors[max];

int main(int argc, char **argv)
{
  for (int i = 2; i < max; i++) {
    if (prime_factors[i]) continue; // it’s composite

    for (int j = i; j < max; j += i) {
      struct entry *e = malloc(sizeof(*e));
      if (!e) croak();

      e->n = i;
      e->next = prime_factors[j];
      prime_factors[j] = e;
    }
  }

  for (;;) {
    char inbuf[80];
    printf("? ");
    fflush(stdout);
    if (!fgets(inbuf, sizeof inbuf, stdin)) { // EOF on input
      printf("quit\n");
      break;
    }

    int n = atoi(inbuf);

    if (n < 0) {
      printf("Only positive numbers.\n");
      continue;
    }

    if (n >= max) {
      printf("Recompile with max > %d to ask that question.\n", max);
      continue;
    }

    printf("Prime factors of %d: {", n);

    int first = 1;
    for (struct entry *e = prime_factors[n]; e; e = e->next) {
      if (!first) printf(" ");
      printf("%d", e->n);
      first = 0;
    }
    printf("}\n");
  }

  return 0;
}