闲题解答
有朋友问我一道题：
采取枚举法，可以计算出答案是 4 和 13. 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#include"iostream"
#include"vector"
using namespace std;
int noks[105]; //not OK sum
int nokp[105]; //not OK product
vector<int> prime;
int main () {
//Find primes first
prime.push_back(2);
for (int i=3;i<=100;i++) {
bool flag = false;
for (int j=2;j*j<=i;j++) {
if (i%j==0) flag = true;
}
if (!flag) prime.push_back(i);
}
//Find sum that is not OK
for (int u:prime) for (int v:prime) {
if (u+v<=100) noks[u+v] = 1;
}
//Find product that is not OK
for (int v=2;v<100;v++) {
int cnt = 0;
for (int d=2;d*d<=v;d++) {
if (v%d==0 and d!=v) {
if (!noks[d+v/d]) cnt++;
}
}
if (cnt!=1) nokp[v] = 1;
}
//The last "Now I too!" statement seems complicated, so i guess i should brute force.
//What Sophie knows: sum, nokp[]
//What Paul knows: product: noks[]
for (int v=2;v<100;v++) {
if (noks[v]) continue;
int product = 0;
for (int a=2;a+a<v;a++) {
int b = v-a; if (b<=2) continue;
if (!nokp[a*b]) {
if (product) {
product = 0;
break;
}
else product = a*b;
}
}
if (product) cout<<v<<" "<<product<<endl;
}
}