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

---
 euler120.c          | 24 ++++++++++++++++++++++++
 euler72.c           | 35 +++++++++++++++++++++++++++++++++++
 euler72_alt_slow.sh | 20 ++++++++++++++++++++
 3 files changed, 79 insertions(+)
 create mode 100644 euler120.c
 create mode 100644 euler72.c
 create mode 100755 euler72_alt_slow.sh

diff --git a/euler120.c b/euler120.c
new file mode 100644
index 0000000..48e63e6
--- /dev/null
+++ b/euler120.c
@@ -0,0 +1,24 @@
+#include <stdio.h>
+
+/*   (a-1)^n + (a+1)^n mod a^2
+ * = n*a*(-1)^(n-1) + (-1)^n + n*a + 1
+ * = na*[(-1)^(n-1)+1] + (-1)^n + 1
+ * = if (n is odd) 2na else 2
+ */
+
+int rmax(int a)
+{
+	int n = a / 2;
+	if (a % 2 == 0)
+		n--;
+	return 2 * n * a;
+}
+
+int main()
+{
+	int sum = 0;
+	for (int a = 3; a <= 1000; a++)
+		sum += rmax(a);
+	printf("%d\n", sum);
+}
+
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);
+}
diff --git a/euler72_alt_slow.sh b/euler72_alt_slow.sh
new file mode 100755
index 0000000..3a8514e
--- /dev/null
+++ b/euler72_alt_slow.sh
@@ -0,0 +1,20 @@
+#!/bin/bash
+
+euler_phi() {
+	prime_factors=($(factor $1 | cut -d ' ' -f2- | tr ' ' '\n' | sort -u))
+	t=$1
+	for i in ${prime_factors[@]}
+	do
+		t=$(($t/$i*($i-1)))
+	done
+	echo $t
+}
+
+sum=0
+i=2
+while [[ $i -le 1000000 ]]
+do
+	sum=$(($sum+$(euler_phi $i)))
+	i=$(($i+1))
+done
+echo $sum
-- 
cgit v1.2.3