题意 哥德巴赫猜想: 任一大于 2 的数都可以分为两个质数之和
给一个 n 分成两个质数之和
线行筛打表即可 可以拿一个数组当桶标记一下 a[i] i 这个数是不是素数 在线性筛后面加个装桶循环即可
- #include<cstdio>
- #include<cstring>
- using namespace std;
- bool Is_Primes[1000005];
- int Primes[1000005];
- int cnt;
- void Prime(int n){
- cnt=0;
- memset(Is_Primes,0,sizeof(Is_Primes));
- for(int i=2;i<=n;i++){
- if(!Is_Primes[i])
- Primes[cnt++]=i;
- for(int j=0;j<cnt&&i*Primes[j]<=n;j++){
- Is_Primes[Primes[j]*i]=1;
- if(i%Primes[j]==0)break;
- }
- }
- memset(Is_Primes,0,sizeof(Is_Primes));
- for(int i=0;i<cnt;i++){
- Is_Primes[Primes[i]]=1;
- }
- }
- int main(){
- int n;
- Prime(1000003);
- while(scanf("%d",&n)==1&&n){
- int temp=0;
- for(int i=0;i<cnt&&Primes[i]<n;i++){
- // printf("%d \n",i);
- if(Is_Primes[n-Primes[i]]==1){
- printf("%d = %d + %d\n",n,Primes[i],n-Primes[i]);
- break;
- }
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2923275.html