euler69.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <stdio.h>

int euler_phi(int n)
{
	int phi = n;

	if (n % 2 == 0) {
		while (n % 2 == 0)
			n /= 2;
		phi /= 2;
	}

	for (int i = 3; i*i <= n; i++) {
		if (n % i == 0) {
			while (n % i == 0)
				n /= i;
			phi /= i;
			phi *= (i-1);
		}
	}

	if (n > 1)
		phi = phi / n * (n-1);

	return phi;
}

int main()
{
	int res;
	double max_n_div_phi = 0;
	for (int i = 2; i <= 1000000; i++) {
		double n_div_phi = (double)i / euler_phi(i);
		if (n_div_phi > max_n_div_phi) {
			res = i;
			max_n_div_phi = n_div_phi;
		}
	}

	printf("%d\n", res);
}