From f54a9727f09e0ffe52f4123ed3f9e0cd67ddcff9 Mon Sep 17 00:00:00 2001 From: Iru Cai Date: Tue, 29 May 2018 21:05:53 +0800 Subject: 69, 71, 81 --- euler69.c | 41 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 41 insertions(+) create mode 100644 euler69.c (limited to 'euler69.c') 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 + +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); +} -- cgit v1.2.3