CODEVS 3205 质数间隙

题目描述 Description

两个连续质数p和q的差d,称为一个长度为d的质数间隙。例如23到29之间的质数间隙长度为6。输入正整数n,编程计算包含n的质数间隙长度。注意,当n为质数时,计算结果为0。

输入描述 Input Description

第一行是正整数t(≤1000),表示数据组数;接下来的t行,每行一个正整数n(≤106)。

输出描述 Output Description

对于每个n,输出包含n的质数间隙长度。

样例输入 Sample Input

3

11

27

492170

样例输出 Sample Output

0

6

114

数据范围及提示 Data Size & Hint

没有!

#include<cstdio>
#include<cmath>
int p(int x){
    int a = sqrt(x);
    for(int i=2;i<=a;i++)if(x%i==0)return 0;
    return 1;
}
int n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
    	int a,j,k;
		scanf("%d",&a);
    	for(j=a;!p(j);j++);
    	for(k=a;!p(k);k--);
    	printf("%d\n",j-k);
	}
}

 

此条目发表在CODEVS分类目录。将固定链接加入收藏夹。