哥德巴赫猜想[洛谷 P1304]

阅读：评论：0

哥德巴赫猜想[洛谷 P1304]

题目描述

输入一个偶数 N(N<=10000)N(N<=10000)，验证4~N所有偶数是否符合哥德巴赫猜想：任一大于 2 的偶数都可写成两个质数之和。如果一个数不止一种分法，则输出第一个加数相比其他分法最小的方案。例如 10，10=3+7=5+5，则 10=5+5 是错误答案。

输入格式

第一行N

输出格式

4=2+2
6=3+3
……
N=x+y

猜想原理

注：这个部分不看也对写代码没有任何影响

哥德巴赫1742年给欧拉的信中哥德巴赫提出了以下猜想：任一大于2的整数都可写成三个质数之和 [1] 。但是哥德巴赫自己无法证明它，于是就写信请教赫赫有名的大数学家欧拉帮忙证明，但是一直到死，欧拉也无法证明。 [2] 因现今数学界已经不使用“1也是素数”这个约定，原初猜想的现代陈述为：任一大于5的整数都可写成三个质数之和。(n>5：当n为偶数，n=2+(n-2)，n-2也是偶数，可以分解为两个质数的和；当n为奇数，n=3+(n-3)，n-3也是偶数，可以分解为两个质数的和)欧拉在回信中也提出另一等价版本，即任一大于2的偶数都可写成两个质数之和。今日常见的猜想陈述为欧拉的版本。把命题"任一充分大的偶数都可以表示成为一个素因子个数不超过a个的数与另一个素因子不超过b个的数之和"记作"a+b"。1966年陈景润证明了"1+2"成立，即"任一充分大的偶数都可以表示成二个素数的和，或是一个素数和一个半素数的和"
今日常见的猜想陈述为欧拉的版本，即任一大于2的偶数都可写成两个素数之和，亦称为“强哥德巴赫猜想”或“关于偶数的哥德巴赫猜想”。
从关于偶数的哥德巴赫猜想，可推出：任何一个大于7的奇数都能被表示成三个奇质数的和。后者称为“弱哥德巴赫猜想”或“关于奇数的哥德巴赫猜想”。若关于偶数的哥德巴赫猜想是对的，则关于奇数的哥德巴赫猜想也会是对的。2013年5月，巴黎高等师范学院研究员哈洛德·贺欧夫各特发表了两篇论文，宣布彻底证明了弱哥德巴赫猜想。

声明

首先我先声明一下，这次的题解我会详细说明代码，也对久违的更新说声抱歉哈。

思路

这道题大概就是递归
首先我们定义两个函数
第一个函数是判断质数的
第二个函数是把n分成x + y

代码解析

int prime(int x)//这个函数是判断一个数是不是质数的
{for(int i=2;i<=sqrt(x);i++)//i的初始值为什么是2以及为什么停止到sqrt（x）请看下面解析{if(x%i==0)	return 1;}return 0;
}

这个函数是判断一个数是不是质数的
首先如果i的初始值为1的话，那么大家想想是不是质数就过去了呢。
既然如此我们就把它设为2。
再说为什么停止到sqrt（x）呢，首先sqrt是开根的意思，因为在x里：1~sqrt（x）乘上任意一个数（可以是循环小数）都可以等于x，并且1到sqrt（x）又小，可以节省时间。

第二部分

int Goldbach(int n)
{for(int i=2;i<=n/2;i++)//看下面分析{if(prime(i)==0 && prime(n-i)==0)//因为i+（n-i）等于n{a=i;b=n-i;return 1;}}return 0;
}

首先我们知道2不是质数，后边的范围只是为了洁身时间。

整段代码

#include <bits/stdc++.h>
using namespace std;
int n,a,b; 
int prime(int x)
{for(int i=2;i<=sqrt(x);i++){if(x%i==0 && i!=1)	return 1;}return 0;
} 
int Goldbach(int n)
{for(int i=2;i<=n/2;i++){if(prime(i)==0 && prime(n-i)==0){a=i;b=n-i;return 1;}}return 0;
}
int main()//听说点赞再走的可以暴富脱单哟
{cin>>n;for(int i=1;i<=n;i++){if(i%2==0 && prime(i))if(Goldbach(i))	cout<<i<<"="<<a<<"+"<<b<<endl;}return 0;
}