2018-5-23

驗證哥德巴赫猜想，直接將素數(shù)全部篩出來，然后從小到大枚舉即可，找到的第一個滿足條件的肯定就是差值最大的即滿足題意的。

普通篩素數(shù)：

#include<iostream> #include<cstring> using namespace std;const int N = 1000000; bool isprime[N+1]; int prime[N+1];void init(){memset(isprime,true,sizeof(isprime));int cnt=0;isprime[2]=true;for (int i=2;i<=N;i++){if (!isprime[i]) continue;prime[cnt++]=i;for (int j=i*2;j<=N;j+=i){isprime[j]=false;}} }int main(){int n;init();while (cin>>n){if (n==0) break;bool flag=false;for (int i=3;i<=n/2+1;i++){if (isprime[i]&&isprime[n-i]){flag=true;cout<<n<<" = "<<i<<" + "<<n-i<<endl;break;}}if (!flag) cout<<"Goldbach's conjecture is wrong."<<endl;} }

線性篩素數(shù)：

#include<iostream> #include<cstring> using namespace std;const int N = 1000000; bool isprime[N+1]; int prime[N+1];void init(){memset(isprime,true,sizeof(isprime));int cnt=0;isprime[2]=true;for (int i=2;i<=N;i++){if (isprime[i]) prime[cnt++]=i;for (int j=0;j<cnt&&i*prime[j]<=N;j++){isprime[i*prime[j]]=false;if (i%prime[j]==0) break;}} }int main(){int n;init();while (cin>>n){if (n==0) break;bool flag=false;for (int i=3;i<=n/2+1;i++){if (isprime[i]&&isprime[n-i]){flag=true;cout<<n<<" = "<<i<<" + "<<n-i<<endl;break;}}if (!flag) cout<<"Goldbach's conjecture is wrong."<<endl;} }

總結(jié)

以上是生活随笔為你收集整理的poj 2262 Goldbach's Conjecture（筛素数）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。