summaryrefslogtreecommitdiff
path: root/euler347.c
diff options
context:
space:
mode:
Diffstat (limited to 'euler347.c')
-rw-r--r--euler347.c88
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);
+}