孪生素数问题--nyoj26

 1 /*孪生素数  终于不超时啦  把判断素数的部分放在while外面减少不必要的用时*/
 2 #include
 3 #include
 4 #define N 1000005
 5 int prime[N];
 6 int main()
 7 {
 8    int i, j,flag,T,M;
 9    for(i=2; i<=N; i++)//*筛选偶数/利用筛选法求素数
10           if(i%2==0&&i>2) prime[i]=0;
11           else prime[i]=1;
12      for(i=3; i<=(int)sqrt(N); i+=2)//奇数/
13        {   if(prime[i])
14            for(j=i+i; ji)
15                 prime[j]=0;
16        }
17    scanf("%d",&T);
18    while(T--)
19    {
20        scanf("%d",&M);
21        for(i=M,flag=0; i>=2; i--)
22         if((prime[i]&&prime[i-1])||(prime[i]&&prime[i-2])) flag++;
23         printf("%d\n",flag);
24    }
25    return 0;
26 }