P1304 哥德巴赫猜想 题解

小邱 · 2021-01-27 12:40:17 · 个人记录

又是刷入门提的一天呐 这是一道非常难水的题 题目传送门：哥德巴赫猜想

好像总共就考察两个点：

1：判断指数

这个。。。只要从2到int(sqrt(n))枚举都没有可以除开n的数就行。这里不做过多解释

2：循环结构

这个。。。不说了。

so

上代码！

#include<iostream> 
using namespace std;
int tr(int x)//判断质数
{
  int n;
  bool a=0;
  for(n=2;n*n<=x;n++)
  {
      if(x%n==0)
          a=1;
  }
    return a;
}
int main() 
{
    int a,n,x;
    cin>>n;
    for(a=4;a<=n;a+=2)//4到n的简单枚举
    {
        for(x=2;x<=a/2;x++)//到a/2，因为如果超过a/2就重复了（虽然肯定有解，到不了a/2+1，但还是写上，显得自己很厉害，是不是
        {
            if(tr(x)==0)//如果x是质数
            {//这里分成两个if是因为如果x不是质数，就不继续判断了，会节省一点时间
                if(tr(a-x)==0)//如果a-x也是质数
                {
                    cout<<a<<"="<<x<<"+"<<a-x<<endl;//输出
                    break;//由于已经找到解了，所以为了不浪费时间和多输出，break
                }
            }
        }
    }
    return 0;
}

其实我的方法不是最优解，因还为可以打表或质数筛等等

最后的最后，

AC记录！