问题描述:
哥德巴赫猜想认为:不小于4的偶数都可以表示为两个素数的和。
你不需要去证明这个定理,但可以通过计算机对有限数量的偶数进行分解,验证是否可行。
实际上,一般一个偶数会有多种不同的分解方案,我们关心包含较小素数的那个方案。
对于给定数值范围,我们想知道这些包含较小素数方案中最大的素数是多少。
比如,100以内,这个数是19,它由98的分解贡献。
你需要求的是10000以内,这个数是多少?
注意,需要提交的是一个整数,不要填写任何多余的内容(比如,说明性的文字)
这个题并不算很难,我认为比较难读的是题意。我当时迷了好久,一直以为就是求一个9998的质数分解,然后把最小的那个质数求出来就行。思考了一会,才发现是每一个偶数分解,总会存在一个最小的质数与一个最大的质数,我们只需要把题意给定那个最小质数的集合求出来,再从最小质数里面筛选出一个最大的就行。
明白了这个东西,这个题直接暴力即可。
代码如下:
#include <iostream> #include <vector> #include <cmath> using namespace std; int main() { int check(int i); int temper=0; vector<int> a; for(int i=2;i<=10000;i++) // 创建一个质数数组。 if(check(i)) a.push_back(i); for(int i=4;i<=10000;i+=2) for(int j=0;j<a.size();j++) if(check(i-a[j])) // 求最小质数,那么就直接按顺序求即可。 { temper=max(temper,a[j]); break; } cout << temper << endl; return 0; } int check(int i) { if(i<=1) return 0; for(int j=2;j<=sqrt(i);j++) if(i%j==0) return 0; return 1; }