题解 P1579 【哥德巴赫猜想（升级版）】

dudujerry · 2018-09-08 15:28:10 · 题解

看到质数想到欧拉筛

数据范围是 20000，线性的复杂度肯定是对的（废话）

但是这道题如果用欧拉筛的话有点小坑

因为我采取的是

1.预处理出1~n的所有质数

2.枚举前两位

3.判断是否（ n - p r i m e [ i ] - p r i m e [ j ] ）是否是质数

重点！

有可能这个数小于2。。。我卡了十五分钟。。。

那么下面放代码！

#include<iostream>
#include<cstdio>
using namespace std;
int prime[20002];
int cnt;
bool vis[20002];
void els(int MAXN){
    for(int i=2;i<=MAXN;i++){
        if(!vis[i]){
            prime[cnt++]=i;
        }
        for(int j=0;j<cnt;j++){
            if(i*prime[j]>MAXN)
                break;
            vis[prime[j]*i]=1;
            if(i%prime[j]==0)
                break;
        }
    }
}
int main()
{
    int n;
    cin>>n;
    els(n);
    for(int i=0;i<cnt;i++){
        for(int j=0;j<cnt;j++){
            int k=n-prime[i]-prime[j];
            if(k>1&&vis[k]==0){
                cout<<prime[i]<<" "<<prime[j]<<" "<<k;
                return 0;
            }
        }
    }
    return 0;
}