hihoCoder 1493-歌德巴赫猜想
#1493 : 歌德巴赫猜想
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
哥德巴赫猜想认为“每一个大于2的偶数，都能表示成两个质数之和”。 给定一个大于2的偶数N，你能找到两个质数P和Q满足P<=Q并且P+Q=N吗？输入
一个偶数N(4 <= N <= 1000000)输出
输出P和Q。如果有多组解，输出P最小的一组。- 样例输入
-
10
- 样例输出
-
3 7
给定一个大于2的偶数N，找出两个质数P和Q，满足P<=Q且P+Q=N。 我还以为这题有什么数论技巧，没想到直接从小到大暴力枚举P就行了。。。 代码如下： [cpp] #include<cstdio> #include<cmath> #include<iostream> using namespace std; bool isPrim(int x) { if (x < 2)return false; for (int i = 2; i <= sqrt(x); ++i) { if (x%i == 0)return false; } return true; } int main() { int N; scanf("%d", &N); for (int i = 2; i <= N / 2; ++i) { if (isPrim(i) && isPrim(N – i)) { printf("%d %d\n", i, N – i); return 0; } } return 0; } [/cpp] 本代码提交AC，用时0MS。]]>