素数槽
Description
处于相邻的两个素数p和p + n之间的n
- 1个连续的合数所组成的序列我们将其称为长度为n的素数槽。比如，‹24, 25, 26, 27, 28›是处于素数23和素数29之间的一个长度为6的素数槽。
你的任务就是写一个程序来计算包括整数k的素数槽的长度。假设k本身就是素数，那么觉得包括k的素数槽的长度为0。
Input
第一行是一个数字n，表示须要測试的数据的个数。后面有n行，每行是一个正整数k。k大于1而且小于或等于的第十万个素数（也就是1299709）。
Output
对于输入部分输入的每个k。都相应输出一个非负整数，表示包括k的素数槽的长度。每个非负整数占一行。
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;
}