题目描述如果n和n+2都是素数，我们称其为孪生素数，比如3和5，5和7都是孪生素数。 给你一个区间[a,b],请问期间有多少对孪生素数？ 输入第一行是一个整数K(K≤ 10000)，表示样例的个数。 以后每行一个样例，为两个整数，a和b，1≤a≤b≤5000000。 输出每行输出一个样例的结果。 样例输入5 1 3 1 10 1 100 1 1000 1 5000000 样例输出0 2 8 35 32463 | ||
AC代码
#include<stdio.h>
#define N 5000005
int a[N]={};
int f[N]={};
void init(){
int i,j;
a[0]=1,a[1]=1;
//埃筛
for(i=2;i<N;i++){
if(a[i]==0){
for(j=2*i;j<N;j+=i){
a[j]=1;
}
}
}
for(i=1;i<N;i++){
if(a[i]==0&&a[i+2]==0){
f[i+2]=1;
}
}
for(i=0;i<N;i++){
f[i]+=f[i-1];
}
}
void sol(){
int a,b;
scanf("%d%d",&a,&b);
//此处是f[b]-f[a-1]
printf("%d\n",f[b]-f[a+1]);
}
int main()
{
int T;
scanf("%d",&T);
init();
while(T--){
sol();
}
} 解题思路:利用埃筛筛选素数，如果a[i]和a[i+2]均为素数，3、5，则f[5]=1。5,7,则f[7]=f[5]++。如果用传统前缀和f[b]-f[a-1]计算，例如a=4,b=10,结果为2，但是满足要求的只有5和7这一对，所以这里采用f[10]-f[5]进行计算，即f[b]-f[a+1]。