kuangbin专题十四 LightOJ1259 素数筛

本文主要是介绍kuangbin专题十四 LightOJ1259 素数筛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
T组询问，每组询问是一个偶数n，验证哥德巴赫猜想，回答n=a+b 且a，b(a<=b)是质数的方案个数。
题解：
用素数筛做这道题就可以了，然后这道题的内存好像不够开太多int，所以再判断素数的时候用bool，然后存放的数组要/10就可以过了。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int MAXN=1e7+7;
bool prime[MAXN];//判断是否为素数。 
int a[MAXN/10],m=0;//存放素数 
int n;
void Prime()
{prime[0]=prime[1]=false,prime[2]=true;for(int i=3;i<MAXN;i++){if(i%2) prime[i]=true;else prime[i]=false;}for(int i=3;i<=sqrt(MAXN);i++){if(prime[i])for(int j=i+i;j<MAXN;j+=i)prime[j]=false;}for(int i=2;i<MAXN;i++)if(prime[i])a[m++]=i;
}
int main()
{Prime(); int t,k=1;scanf("%d",&t);while(t--){int ans=0;scanf("%d",&n);for(int i=0;i<m&&a[i]<=n/2;i++) //n/2是保证不重复计算，然后也保证题目的a<=b; {int tmp=n-a[i];if(prime[tmp])ans++;}printf("Case %d: %d\n",k++,ans);} 
} 

这篇关于kuangbin专题十四 LightOJ1259 素数筛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---