From d1be3105ba259970ebfcf71370fb4baca89abd86 Mon Sep 17 00:00:00 2001
From: Iru Cai <mytbk920423@gmail.com>
Date: Sun, 27 May 2018 14:05:48 +0800
Subject: 72,120

---
 euler72.c | 35 +++++++++++++++++++++++++++++++++++
 1 file changed, 35 insertions(+)
 create mode 100644 euler72.c

(limited to 'euler72.c')

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);
+}
-- 
cgit v1.2.3