思特奇杯·云上蓝桥-算法集训营】第1周 哥德巴赫分解

本文主要是介绍思特奇杯·云上蓝桥-算法集训营】第1周 哥德巴赫分解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

问题描述：

哥德巴赫猜想认为：不小于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;
}

这篇关于思特奇杯·云上蓝桥-算法集训营】第1周 哥德巴赫分解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！