首页 > 代码库 > 青岛理工交流赛 H题 素数间隙
青岛理工交流赛 H题 素数间隙
13110581088注销
素数间隙
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的素数间隙的长度，不应有其他字符出现在输出中。
示例输入
1011272492170
示例输出
4060114
提示
来源
青岛理工交流赛
示例程序
算法分析： 素数筛 筛好范围的素数标记下。 然后判断一下，f[n]是不是素数，如果是就输出0，否则往标记数组两边走，直到找到两端的素数，
把它们的下标相减输出就行了，1Y ！
#include <iostream>#include <string>#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;int f[1300000];void sushushai(){ memset(f, 0, sizeof(f)); f[1]=1; int i, j; i=2; while(i<=10000) { for(j=i*2; j<=1299710; j+=i) { f[j]=1; //不是素数 } i++; while(f[i]==1) { i++; } }}int main(){ sushushai(); int n; int dd, j; while(cin>>n) { if(f[n]==0 ) //如果本身就是素数 { cout<<"0\n"; } else { j=n-1; dd=n+1; while( f[j]==1 ) { j--; } while( f[dd]==1 ) { dd++; } cout<<dd-j<<endl; } } return 0;}
青岛理工交流赛 H题 素数间隙
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。