AcWing 1292. 哥德巴赫猜想
原题链接
简单
作者:
kRYST4L
,
2023-05-27 12:39:40
,
所有人可见
,
阅读 153
算法过程
- 先用欧拉筛预处理出2-1000000中的所有质数
- 然后分析一下数字性质,由于n是偶数且要求组成n的两个数为奇素数
- 那么根据偶数=奇数+奇数的性质,只要有一个是奇数,另外一个必是奇数
- 并且在所有的素数集里除了2是偶数外,其他所有质数都为奇数,所以我们不需要去判断i素数是否为奇数
- 我们只需要去判断n-primes[i]是否是素数即可,利用st[n-primes[i]]判断是否是素数
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
int primes[N];
bool st[N];
int cnt;
int n;
void get_primes(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i]) primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++)
{
st[i*primes[j]]=true;
if(i%primes[j]==0) break;
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
get_primes(1000000);
int n;
while(cin>>n,n)
{
int flag=0;
for(int i=0;i<cnt;i++)
{
if(!st[n-primes[i]])
{
printf("%d = %d + %d\n",n,primes[i],n-primes[i]);
flag=1;
break;
}
}
if(!flag) cout<<"Goldbach's conjectrue is wrong."<<endl;
}
}