blob: c1ab1661887ea282c2ec344eba7c5e74368591fb (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
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);
}
|
