C++题解：哥德巴赫猜想

 目录

题目 

题解

题目 

•  1000ms
•  131072K

1742 年 6 月 7 日哥德巴赫写信给当时的大数学家欧拉，正式提出了以下的猜想：任何一个大于 5 的奇数都可以表示成 3 个质数之和。

这就是哥德巴赫猜想。欧拉在回信中说，他相信这个猜想是正确的，但他不能证明。

现在请你编一个程序验证哥德巴赫猜想。

输入格式

第一个奇数 n (5

输出格式

输出三个用空格分隔的质数，如果有多个答案，输出字典序最小的。

输出时每行末尾的多余空格，不影响答案正确性

要求使用「文件输入输出」的方式解题，输入文件为 goldbach.in，输出文件为 goldbach.out

样例输入

119

样例输出

3 3 113

题解：

知识点：数学

分析：题目比较简单，先用埃氏筛法预处理出质数，再一个一个去枚举

代码：

#include
#include
#include
using namespace std;
const int N=1e5+5;
bool vis[N];//vis[i]表示i是否是质数，true是“不是”
int main(){int n;scanf("%d",&n);vis[0]=vis[1]=true;//注意0、1for (int i=2;i<=n;i++){//埃氏筛质数法，手动模拟一遍即可理解if (!vis[i]){for (int j=i;j<=n;j+=i){vis[j]=true;}vis[i]=false;}}for (int i=2;i<=n;i++){if (vis[i]){//如果是质数，跳过continue;}for (int j=2;j<=n;j++){if (vis[j] || n-i-j<=1 || vis[n-i-j]){//看看是否符合哥德巴赫猜想，n-i-j是第3个数continue;}int a[3];//排一下序，本人比较懒，不想手写a[0]=i;a[1]=j;a[2]=n-i-j;sort(a,a+3);printf("%d %d %d\n",a[0],a[1],a[2]);return 0;}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！