时间限制：3000 ms | 内存限制：65535 KB 难度：3 描述 写一个程序，找出给出素数范围内的所有孪生素数的组数。一般来说，孪生素数就是指两个素数距离为2，近的不能再近的相邻素数。有些童鞋一看到题就开始写程序，不仔细看题，咱们为了遏制一下读题不认真仔细的童鞋，规定，两个素数相邻为1的也成为孪生素数。 输入 第一行给出N(0<N<100)表示测试数据组数。 接下来组测试数据给出m，表示找出m之前的所有孪生素数。 (0<m<1000000) 输出 每组测试数据输出占一行，该行为m范围内所有孪生素数组数。 样例输入 1 14 样例输出 4 素数筛选法抽象对的来讲就是将2的倍数，3的倍数，5的倍数。。。都去掉剩下的就是素数。 代码如下
for(int i=1;i<maxx;i++) { if(i%2==0) a[i]=0; else a[i]=1; } for(int i=3;i<maxx;i++) { if(a[i]==1) { for(int j=i*2;j<maxx;j+=i) { a[j]=0; } } }题目代码如下
#include<iostream> #include<cstdio> using namespace std; #define maxx 1000050 int a[maxx]; int main() { int N; for(int i=1;i<maxx;i++) { if(i%2==0) a[i]=0; else a[i]=1; } a[2]=1; a[1]=0; for(int i=3;i<maxx;i++) { if(a[i]==1) { for(int j=i*2;j<maxx;j+=i) { a[j]=0; } } } scanf("%d",&N); int m; while(N--) { scanf("%d",&m); int sum=0; for(int i=2;i<m;i++) { if(a[i]==1&&a[i+1]==1) sum++; if(a[i]==1&&a[i+2]==1&&(i+2<=m)) sum++; } printf("%d\n",sum); } return 0; }