素数槽

Description

Input

Output

Sample Input

5
10
11
27
2
492170

Sample Output

4
0
6
0
114

题意：

两个素数之间所有为连续的合数，一共同拥有n个这种数。那么这个素数槽的个数为n+1。题目给定你一个数，问你这个数在某个素数槽中。求这个素数槽的个数。

思路：

假设输入的数为素数，那么素数槽的个数为0,。
假设为合数。就从这个数開始，往左右两边分别递减或递增一个数，每次累计记录，直到遇到素数为止。

代码例如以下：

#include<cstdio>
bool p[1299710];
#include<cstring>
using namespace std;
void prime()
{
    int i,j;
     memset(p,0,sizeof(p));
    for(int i=2;i<=1299709;i++)
        {
           if(!p[i])
           {
               for(int j=2;i*j<=1299709;j++)
                p[i*j]=1;
           }
        }
}
int main()
{
    int n,a,sum,k,t;
    prime();
   scanf("%d",&n);
    while(n--)
    {
        sum=0;
        scanf("%d",&a);
        if(!p[a]||a==1)
          {
             printf("%d\n",sum);
              continue;
          }
        t=a;
        while(a--)
        {
            if(p[a])
            sum+=1;
            else
                break;

        }
        while(t++)
        {
            if(p[t])
            sum+=1;
            else
                break;
        }

printf("%d\n",sum+2);

    }
    return 0;
}