NYOJ-26 孪生素数问题

时间限制： 3000 ms  |  内存限制： 65535 KB 难度： 3 描述 写一个程序，找出给出素数范围内的所有孪生素数的组数。一般来说，孪生素数就是指两个素数距离为2，近的不能再近的相邻素数。有些童鞋一看到题就开始写程序，不仔细看题，咱们为了遏制一下读题不认真仔细的童鞋，规定，两个素数相邻为1的也成为孪生素数。 输入 第一行给出N(0<N<100)表示测试数据组数。 接下来组测试数据给出m，表示找出m之前的所有孪生素数。 (0<m<1000000) 输出 每组测试数据输出占一行，该行为m范围内所有孪生素数组数。 样例输入 1 14 样例输出 4 //筛选法求素数 #include <stdio.h> #define M 1000005 int prime[1000];   //存放素数 int judge[M];      //标记数组 int main() {     int n,m,i,j,cnt,num=0; //    for(i=2;i*i<=M;i++)     // 第一种筛法 //        for(j=2;j*i<=M;j++) //            prime[i*j]=1;     for(i=2;i<M;i++)        //这个是第二种筛法，定义两个数组，一个存放素数，一个做标记。                                     //注意这两个筛选法，在下面查找孪生素数是的判断条件也不同。    {         if(judge[i]==0)             prime[num++]=i;         for(j=0; j<num&&i*prime[j]<=M; j++)         {             judge[i*prime[j]]=1;             if(i%prime[j]==0)                 break;         }     }     for(i=2;i<100;i++)         if(prime[i]==0)             printf("%-3d",i);     scanf("%d",&n);     while(n--)     {         cnt=0;         scanf("%d",&m);         for(i=0;prime[i]<=m;i++)         {            //    if(prime[i]==0&&prime[i-2]==0)  //第一种方法的 判断语句             if(prime[i]-prime[i-1]==2)                 cnt++;         }         if(m<=2)             printf("0\n");         else             printf("%d\n",cnt);     }     return 0; }