NOIP2010年第十六届普及组初赛完善程序题:(哥德巴赫猜想)哥德巴赫猜想是指,任一大于 2 的偶数都可写成两个质数之和。迄今 为止,这仍然是一个著名的世界难题,被誉为数学王冠上的明珠。试编写程序,验证任一大 于 2 且不超过 n 的偶数都能写成两个质数之和。
#include <iostream> usingnamespacestd; int main() { constint SIZE = 1000; int n, r, p[SIZE], i, j, k, ans; bool tmp; cin>>n; r = 1; p[1] = 2; for (i = 3; i <= n; i++) { [ ① ]; for (j = 1; j <= r; j++) if (i % [ ② ] == 0) { tmp = false; break; } if (tmp) { r++; [ ③ ] ; } } ans = 0; for (i = 2; i <= n / 2; i++) { tmp = false; for (j = 1; j <= r; j++) for (k = j; k <= r; k++) if (i + i == [ ④ ] ) { tmp = true; break; } if (tmp) ans++; } cout<<ans<<endl; return0; }
若输入n为2010,则输出[ ⑤ ]时表示验证成功,即大于2且不超过2010的偶数都满足哥德巴赫猜想。