1 files changed, 41 insertions, 0 deletions
diff --git a/euler69.c b/euler69.c
new file mode 100644
index 0000000..e95a6c2
--- /dev/null
+++ b/euler69.c
@@ -0,0 +1,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);
+}