Prime Gap
这里直接写中文了
Descriptions:
对于一个数n,若n为素数则输出0,否则找到距离n最小的两个素数,一个大于n,一个小于n,输出他们的差(正数)
Input
多组输入
每行包含一个数n
若n为0,程序结束
Output
对于每个测试数据,输出一个答案占一行
Sample Input
10
11
27
2
492170
0
Sample Output
4
0
6
0
114
题目链接:
https://vjudge.net/problem/UVA-1644
水题,先求质数表,预先处理出质数,然后输入n,若n为质数,输出0,若不为,可从第2个质数往后扫,当出现第一个大于n的数时,即可将他减去上一个质数,即为答案。
AC代码
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <sstream> #define mod 1000000007 #define eps 1e-6 #define ll long long #define INF 0x3f3f3f3f #define ME0(x) memset(x,0,sizeof(x)) using namespace std; int T; int n; int isprime[1300005];//判断这里面哪个数是素数 int ans[1300005];//把素数全部存进一个数组,方便查找 void eratos(int x)//求素数表 { for(int i=0; i<=x; ++i) isprime[i]=true; isprime[0]=isprime[1]=false; for(int i=2; i<=x; ++i) { if(isprime[i]) { int j=i+i; while(j<=x) { isprime[j]=false; j+=i; } } } } void solve() { if(isprime[n]) { cout<<0<<endl; return; } else { for(int i=1; ;++i) { if(ans[i]<n&&ans[i+1]>n) { cout<<ans[i+1]-ans[i]<<endl; return; } } } } int main() { int j=-1; eratos(1300005); for(int i=2; i<=1300005; ++i) if(isprime[i]) ans[++j]=i; // for(int i=0; i<=10; ++i) // cout<<ans[i]<<endl; while(cin>>n,n) { solve(); } }