euler72.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

#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()
{
	long long cnt = 0;
	for (int i = 2; i <= 1000000; i++)
		cnt += euler_phi(i);

	printf("%lld\n", cnt);
}