【代码笔记】C++实现哥德巴赫猜想输入型

1.受小学妹的请教，于是写下这个数学问题的计算机算法。

好久没有写过C++的程序，这次还自己去查c++的标准库才把程序写完。

2.问题描述如下：验证欧拉版哥德巴赫猜想，输入一个大于2的偶数，输出该数可以表达成哥德巴赫猜想的方案数目及具体方案。

运行样例：

输入10
输出：
2
10=3+7
10=5+5
(注意：10=7+3为10=3+7的等效方案)

3.代码如下：

#include<iostream>
#include<vector>//对象类型，数组标准库
using namespace std;
using std::vector;
//验证整数是否为素数的函数PrimeFunction
bool PrimeFunction(int num);
//剔除不规范的输入，提高代码的健壮性
int CorrectInt(int cInteger);
int main()
{
    int integer;//输入的待验证数字
    int primeNum1 =1;//分解出来的第一个可能的素数
    int primeNum2;//分解出来的第二个可能的素数
    //结果存到二维数组里

    vector < vector <int> > primeList2;

    cout<<"请输入任何一个大于2的正偶数："<<endl;
    cin>>integer;

    //剔除不规范的输入，提高代码的健壮性
    integer =CorrectInt(integer);

    cout<<"请稍等……"<<endl;
    for(; primeNum1<=integer/2;)
    {
        primeNum2 = integer-primeNum1;
        if(PrimeFunction(primeNum1)&& PrimeFunction(primeNum2))
        {
            vector<int> primeList1;
            primeList1.push_back(primeNum1);
            primeList1.push_back(primeNum2);
            primeList2.push_back(primeList1);
        }
        primeNum1= primeNum1+2;


    }
    if(primeList2.size()!=0)
    {
        cout<<"该素数可分解为"<<primeList2.size()<<"组。"<<endl;
        cout<<"该素数分解为："<<endl;
        for(int j=0; j<primeList2.size(); j++)
        {
            cout<<integer<<"="<<primeList2[j][0]<<"+"<<primeList2[j][1]<<endl;

        }

    }
    else
    {
        cout<<integer<<"不能分解为两素数之和，恭喜你证明了哥德巴赫猜想是错的！"<<endl;
    }

    return 0;
}
//剔除不规范的输入，提高代码的健壮性
int CorrectInt(int cInteger)
{

    while(cInteger<=2||cInteger%2!=0)
    {
        cout<<"输入错误，请输入任何一个大于2的正偶数："<<endl;
        cin>>cInteger;
        cInteger = CorrectInt(cInteger);
    }
    return cInteger;
}

//验证整数是否为素数的函数PrimeFunction
bool PrimeFunction(int num)
{
    if(num==1)
    {
        return true;
    }
    else
    {
        for(int i= 2; i<(num+1)/2; i++)
        {
            if(num%i==0)
            {
                return false;
            }
        }
        return true;
    }

}

4.测试结果如下：

image.png

image.png

image.png

image.png

image.png

5.当然，本程序存在不少缺陷。

• 1）定义数据类型为int型，一旦输入错误字符或者超出int能容纳的数据大小，程序直接奔溃。
• 2）没有使用线程，电脑性能差的，较大的数可能运行等待半天才能打印结果。
• 3）算法还可以进一步优化，这里采用简单的累加遍历。

6.当然，代码结构很简单，就两个计算的函数，然后加一些判断就可以得出结果，最后输出即可。重点是算法实现。

第一次用c++的标准库，查了半小时vector标准库关于二维数组的使用。
不能用普通的数据，因为在用户输入之前，不知道即将存入多少组数据。如下：

int integer[a][b];

c++中a和b是必须提前明确的，所以只能用类似于java中的arrayList。

7.首先需要声明一个vector标准库。搭建好二维数组模型。

#include<vector>//对象类型，数组标准库
using std::vector;

后面那个std一串主要是为了后面少声明，就不用带std使用vector。
然后声明一个一维数组。数据存储内容为int型的一维数组。

vector < vector <int> > primeList2;

而后在之后的创建中，新建里面的一维数组，而且必须在里面创建，分配新的内存地址，不然新的数据会覆盖之前存储的数据。

vector<int> primeList1;

8.0 算法主要分为四个方面。

第一个是剔除不规范的输入，提高代码的健壮性，确定用户输入的是正整数。这里主要运用了递归算法，就像是俄罗斯的套套娃，自己套自己，自己内部调用自己。

//剔除不规范的输入，提高代码的健壮性
int CorrectInt(int cInteger)
{

    while(cInteger<=2||cInteger%2!=0)
    {
        cout<<"输入错误，请输入任何一个大于2的正偶数："<<endl;
        cin>>cInteger;
        cInteger = CorrectInt(cInteger);
    }
    return cInteger;
}

第二个是验证是否为素数。

//验证整数是否为素数的函数PrimeFunction
bool PrimeFunction(int num)
{
    if(num==1)
    {
        return true;
    }
    else
    {
        for(int i= 2; i<(num+1)/2; i++)
        {
            if(num%i==0)
            {
                return false;
            }
        }
        return true;
    }

}

当然这里巧妙的把算法复杂度降低了一半，只需要遍历该数的一半即可判断是否为素数，没必要从2一直遍历到该数额大小。
第三通过循环遍历，进行删选和存储。

 for(; primeNum1<=integer/2;)
    {
        primeNum2 = integer-primeNum1;
        if(PrimeFunction(primeNum1)&& PrimeFunction(primeNum2))
        {
            vector<int> primeList1;
            primeList1.push_back(primeNum1);
            primeList1.push_back(primeNum2);
            primeList2.push_back(primeList1);
        }
        primeNum1= primeNum1+2;
    }

这里也对算法的复杂度降低了4倍。一是只遍历到该数一半，二是从分解成1开始判断，之后直接加2，因为该数不可能分解成一个偶数和另一个数之和，偶数肯定不是素数。
这里还可以进行算法优化的是，2、3的整数倍也可以排除在外，，这样可以提高算法运算效率。
第四是vector标准库的使用，存储和读取。
关键语句为：

vector<int> primeList1;
            primeList1.push_back(primeNum1);
            primeList1.push_back(primeNum2);
            primeList2.push_back(primeList1);

............................................................
 for(int j=0; j<primeList2.size(); j++)
        {
            cout<<integer<<"="<<primeList2[j][0]<<"+"<<primeList2[j][1]<<endl;

        }

这里没有用两个for循环遍历，实在没有必要，除了提高运算时间，一点好处也没有。

9.0最后，总结一下，这虽然是一道大一简单的算法实验，或者说课堂练习题。但基本上需要用到很多思维，对新手来说，是一道比较难以控制和想象的题目，希望能帮到大家，提供一些思路。

END