diff options
Diffstat (limited to 'euler347.c')
-rw-r--r-- | euler347.c | 88 |
1 files changed, 88 insertions, 0 deletions
diff --git a/euler347.c b/euler347.c new file mode 100644 index 0000000..c1ab166 --- /dev/null +++ b/euler347.c @@ -0,0 +1,88 @@ +#include <stdio.h> +#include <string.h> + +#define N 10000000 +//#define N 100 + +int nprimes; +int primes[N]; +int divisor[N+1]; + +void find_primes() +{ + memset(divisor, 0, sizeof(divisor)); + nprimes = 0; + for (int i = 2; i <= N/2; i++) { + if (divisor[i] == 0) { + primes[nprimes] = i; + nprimes++; + } + for (int j = 0; j < nprimes; j++) { + int t = i * primes[j]; + if (t > N) + break; + divisor[t] = i; + } + } +} + +int M(int p, int q, int n) +{ + int r = 0; + long long t1 = p; + while (t1 < n) { + long long t2 = t1 * q; + if (t2 > n) + break; + while (t2 * q <= n) { + t2 *= q; + } + if (t2 > r) + r = t2; + t1 *= p; + } + return r; +} + +int ismpqn(int n) +{ + int npf = 0; + int pf[64]; + + if (divisor[n] == 0) + return 0; + + int t = n; + while (divisor[t] != 0) { + int d = t / divisor[t]; + pf[npf] = d; + npf++; + while (t % d == 0) { + t /= d; + } + } + if (t > 1) { + pf[npf] = t; + npf++; + } + + if (npf != 2) + return 0; + + /* TODO: Maybe it can be optimized, but it looks enough */ + if (M(pf[0], pf[1], N) == n) + return 1; + else + return 0; +} + +int main() +{ + long long s = 0; + find_primes(); + for (int i = 1; i <= N; i++) { + if (ismpqn(i)) + s += i; + } + printf("%lld\n", s); +} |