南京网站做的好的公司,昆明seo关键词排名,p9制作公司,大型建设网站制作题目描述 如果n和n2都是素数#xff0c;我们称其为孪生素数#xff0c;比如3和5#xff0c;5和7都是孪生素数。 给你一个区间[a,b],请问期间有多少对孪生素数#xff1f; 输入 第一行是一个整数K(K≤ 10000)#xff0c;表示样例的个数。 以后每行一个样例#xff0c;为两… 题目描述 如果n和n2都是素数我们称其为孪生素数比如3和55和7都是孪生素数。 给你一个区间[a,b],请问期间有多少对孪生素数 输入 第一行是一个整数K(K≤ 10000)表示样例的个数。 以后每行一个样例为两个整数a和b1≤a≤b≤5000000。 输出 每行输出一个样例的结果。 样例输入 5
1 3
1 10
1 100
1 1000
1 5000000样例输出 0
2
8
35
32463AC代码
#includestdio.h
#define N 5000005
int a[N]{};
int f[N]{};
void init(){int i,j;a[0]1,a[1]1;//埃筛 for(i2;iN;i){if(a[i]0){for(j2*i;jN;ji){a[j]1;}}} for(i1;iN;i){if(a[i]0a[i2]0){f[i2]1;}}for(i0;iN;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[a1]);
}
int main()
{int T;scanf(%d,T);init();while(T--){sol();}}
解题思路:利用埃筛筛选素数如果a[i]和a[i2]均为素数3、5则f[5]1。5,7,则f[7]f[5]。如果用传统前缀和f[b]-f[a-1]计算例如a4,b10,结果为2但是满足要求的只有5和7这一对所以这里采用f[10]-f[5]进行计算即f[b]-f[a1]。
