首页 > 代码库 > SDUT 3002-素数间隙(素数筛+暴力)

SDUT 3002-素数间隙(素数筛+暴力)

素数间隙

Time Limit: 1000ms   Memory limit: 262144K  有疑问?点这里^_^

题目描述

Neko猫是一个很喜欢玩数字游戏的会说话的肥猫,经常会想到很多很好玩的数字游戏,有一天,它想到一个叫做素数间隙的游戏。据Neko猫的定义,素数间隙是两个相邻素数pq组成的开区间[p, q),所以素数间隙的长度就是q-p

例如711在素数表里是两个相邻的素数,所以711的素数间隙的长度为11-7,为4。 

现在Neko猫会给你很多个正整数K1K1299710),让你能立刻求出包含数字K的素数间隙的长度。为方便起见,如果K是素数,则输出0

输入

 

输入包含T组数据(1T1000),每组测试数据占一行,是一个正整数K1K1299710)。

输出

 

输出T行,每行一个非负数,这个非负数是包含输入数字K的素数间隙的长度,不应有其他字符出现在输出中。

示例输入

10
11
27
2
492170

示例输出

4
0
6
0
114
水一发睡觉。。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cctype>
#include <vector>
#include <cstdio>
#include <cmath>
#include <deque>
#include <stack>
#include <map>
#include <set>
#define ll long long
#define maxn 1299730
#define pp pair<int,int>
#define INF 0x3f3f3f3f
#define max(x,y) ( ((x) > (y)) ? (x) : (y) )
#define min(x,y) ( ((x) > (y)) ? (y) : (x) )
using namespace std;
int pri[maxn],n;
void init()
{
	memset(pri,1,sizeof(pri));
	pri[1]=0;
	for(int i=2;i<maxn;i++)
	{
		if(pri[i])
		{
			for(int j=2;j*i<maxn;j++)
				pri[i*j]=0;
		}
	}
}
int main()
{
	init();
	while(~scanf("%d",&n))
	{
		if(pri[n])
		{
			puts("0");
			continue;
		}
		int l=n,r=n;
		while(!pri[--l]);
		while(!pri[++r]);
		printf("%d\n",r-l);
	}
	return 0;
}


SDUT 3002-素数间隙(素数筛+暴力)