Problem Description
在连续自然数[l,r]中找出任意三个连续的素数a、b、c，如果a+b+c的和也为一个素数，那么我们就称这样的三个素数a、b、c为一组友好素数对。
注意：例如5,7,11就是三个连续的素数（即两个素数之间没有其他素数间隔，就可以说这两个素数连续），并且它们的和为23，也是一个素数。
Input 第一行输入一个整数T，表示数据组数（1< T<10000）； 第二行输入两个数据l,r（1<=l、r<=10^6)；
Output 每组数据输出友好素数对的总组数。
Sample Input 2 5 11 1 100
Sample Output 1 15
考查思维和代码实现了，需要一定的acm基础。在校赛的时候，为了卡时间，需要很多数据，为此我也破费周折。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define m 1000005 long long d[1000010],s[1000010],cnt=0; int is_prime(int x) { for(int i=2;i*i<=x;i++) if(x%i==0) return 0; return 1; } void Init() { long long i,j; memset(d,0,sizeof(d)); for(i=2;i<=m;i++) if(d[i]==0) for(j=i*i;j<=m;j+=i) d[j]=1; for(i=2;i<=m;i++) if(d[i]==0) d[cnt++]=i; d[cnt]='\0'; } int find(int x) { int l=0,r=cnt-1; while(l<=r) { int mid=(l+r)/2; if(x<d[mid]) r=mid-1; else l=mid+1; } return l; } int main() { Init(); //素数打表 s[0]=s[1]=0; for(int i=2;i<cnt;i++) //预处理s[]数组 { if(is_prime(d[i]+d[i-1]+d[i-2])) //判断素数 s[i]=s[i-1]+1; else s[i]=s[i-1]; } for(int i=0;i<100;i++) cout<<d[i]<<": "<<s[i]<<" "; cout<<endl; int t,l,r; scanf("%d",&t); while(t--) { scanf("%d%d",&l,&r); int p=find(l),q=find(r); //二分查找 if(q-p<2) { printf("0\n"); continue; } if(is_prime(l)==0) p++; q--; int ans=s[q]-s[p]; printf("%d\n",ans); } return 0; }