题解：P1304 哥德巴赫猜想

（第一次写题解，新手见谅。）
思路：由题干可知，需输出4~N中所有偶数拆分出的两个质数（素数）且最小（第一个）。
中心思想（核心代码）无疑是判断质数。
根据你渊博的学识可知，判断质数的方法有以下三种：
1.穷举法（暴力）；
2.埃氏筛法（埃拉托色尼筛法）；
3.线性筛法（欧拉筛法）；
4.打表法。
当然你不用懂得这些筛法具体的算法原理及时间复杂度什么的，你只需要记住一下这句话就够了：
若 n 不能不能被 2 到

\sqrt{n}

之间的任何整数整除，则 n 是质数，即下面公式：

\forall k \in \{2, 3, \ldots, \lfloor\sqrt{n}\rfloor\}, \quad n \mod k \neq 0

那就很简单了。
使用库中的sqrt（）函数即可求出平方根。然后依次列举判断就可以了；又因为需多次判断质数，避免过多的代码繁复，我们可以选择用自定义函数选择 bool（布尔值）判断是否为质数，如果第一个数和第二个数都为1 （true）则输出。
运用循环嵌套，外循环从4开始枚举到 n ，内循环从2枚举到i-1， int a，b（a为j，b为i-a）。
话不多说上代码。

CPP

#include<bits/stdc++.h>
using namespace std;
bool zs(int a){//判断质数的函数 
	for(int i=2;i<=sqrt(a);i++){
		if(a%i==0){
			return false;//返回值为0 。
		}
	}
	return true;//返回值为1 。
}
int n;
int main(){
	cin>>n;
	for(int i=4;i<=n;i+=2){
		for(int j=2;j<i-1;j++){
			int a,b;
			a=j,b=i-j;
			if(zs(a)==1 && zs(b)==1){//直接使用函数，判断质数的返回值即可 。
				cout<<i<<"="<<a<<"+"<<b<<endl;
				break;//跳出内循环，直接进入到下一个数，避免输出数据重复。 
			}	
		}		
    }
	return 0;
}

求赞哇。

题解：P1304 哥德巴赫猜想

文章操作

相关推荐

评论

题解：P1304 哥德巴赫猜想