C++ PTA 验证“哥德巴赫猜想”

本文主要是介绍C++ PTA 验证“哥德巴赫猜想”，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

二、算法思路

• 可以先设计一个函数用于判断是否为素数，在素数判断的时候可以不用从2遍历到n-1
• 只需要遍历到根号n即可，2和3小素数还有偶数可以提前进行判断。

• 题目要求的是求两个数p和q，使得p + q = n，而且有多个解时要求输出p最小的情况。
• 所以我们可以对p的值从2到n-1进行遍历，不需要再写一个循环对q的值进行遍历，要是写成双循环的话没法过最大N的样例。
• q的值可以用表达式来表示n - p，如果p和q同时都为素数时，就直接输出结果并结束程序。

三、代码

//作者：小狐狸
#include<iostream>
#include<cmath>
using namespace std;
int sushu(int number){//素数判断,素数返回1，否则返回0if(number==2||number==3)//小素数return 1;if(number%2==0)//偶数判断return 0;for(int i=3;i<=sqrt(number);i++){if(number%i==0)return 0;}return 1;
}
int main(){int n;int p;cin>>n;for(p=2;p<n;p++){if(sushu(i)&&sushu(n-i))//p和q同为素数时{cout<<n<<" = "<<p<" + "<<n-p<<endl;return 0;}}return 0;
}

这篇关于C++ PTA 验证“哥德巴赫猜想”的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---