A40831. 哥德巴赫分解
填空题
困难
知识点
题目描述
哥德巴赫分解
题目描述
哥德巴赫猜想认为：不小于4的偶数都可以表示为两个素数的和。
你不需要去证明这个定理，但可以通过计算机对有限数量的偶数进行分解，验证是否可行。
实际上，一般一个偶数会有多种不同的分解方案，我们关心包含较小素数的那个方案。
对于给定数值范围，我们想知道这些包含较小素数方案中最大的素数是多少。
比如，100以内，这个数是19，它由98的分解贡献。
你需要求的是10000以内，这个数是多少？
参考答案
const int N = 10000;
vector<int>prime;
bool vis[10010];
int ans;
void check(int n) {
for (int i = 0; i < prime.size(); ++i) {
int r = n - prime[i];
if (vis[r]) {
ans = max(ans, prime[i]);
return ;
}
}
}
void solve() {
memset(vis, true, sizeof(vis));
for (int i = 2; i < N; ++i)
if (vis[i])for (int j = i + i; j < N; j += i)vis[j] = false;
for (int i = 2; i < N; ++i)if (vis[i])prime.push_back(i);
for (int i = 4; i < 10000; i += 2)check(i);
cout << ans << "\n";
}答案解析
答案：173
上一题
下一题