diff options
Diffstat (limited to 'euler72.c')
-rw-r--r-- | euler72.c | 35 |
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); +} |