diff options
| -rw-r--r-- | euler120.c | 24 | ||||
| -rw-r--r-- | euler72.c | 35 | ||||
| -rwxr-xr-x | euler72_alt_slow.sh | 20 |
3 files changed, 79 insertions, 0 deletions
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 |