72,120

1 files changed, 35 insertions, 0 deletions

diff --git a/euler72.c b/euler72.c
new file mode 100644
index 0000000..d62c508
--- /dev/null
+++ b/euler72.c
@@ -0,0 +1,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);
+}