首页 > 代码库 > SDUT 3002-素数间隙(素数筛+暴力)
SDUT 3002-素数间隙(素数筛+暴力)
素数间隙
Time Limit: 1000ms Memory limit: 262144K 有疑问?点这里^_^
题目描述
Neko猫是一个很喜欢玩数字游戏的会说话的肥猫,经常会想到很多很好玩的数字游戏,有一天,它想到一个叫做素数间隙的游戏。据Neko猫的定义,素数间隙是两个相邻素数p和q组成的开区间[p, q),所以素数间隙的长度就是q-p。
例如7和11在素数表里是两个相邻的素数,所以7和11的素数间隙的长度为11-7,为4。
现在Neko猫会给你很多个正整数K(1<K≤1299710),让你能立刻求出包含数字K的素数间隙的长度。为方便起见,如果K是素数,则输出0。
输入
输入包含T组数据(1≤T≤1000),每组测试数据占一行,是一个正整数K(1<K≤1299710)。
输出
输出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-素数间隙(素数筛+暴力)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。