本文主要是介绍Prime Gap，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Prime Gap
时间限制: 5 Sec 内存限制: 128 MB
题目描述
The sequence of n ? 1 consecutive composite numbers (positive integers that are not prime and not equal to 1) lying between two successive prime numbers p and p + n is called a prime gap of length n. For example, ?24, 25, 26, 27, 28? between 23 and 29 is a prime gap of length 6.
Your mission is to write a program to calculate, for a given positive integer k, the length of the prime gap that contains k. For convenience, the length is considered 0 in case no prime gap contains k.
输入
The input is a sequence of lines each of which contains a single positive integer. Each positive integer is greater than 1 and less than or equal to the 100000th prime number, which is 1299709. The end of the input is indicated by a line containing a single zero.
输出
The output should be composed of lines each of which contains a single non-negative integer. It is the length of the prime gap that contains the corresponding positive integer in the input if it is a composite number, or 0 otherwise. No other characters should occur in the output.
样例输入
10
11
27
2
492170
0
样例输出
4
0
6
0
114
#include<iostream>
#include<math.h>using namespace std;
#define MAX 1300000
int x[MAX];
//列举所有质数，给定一个数，若为质数，则输出0
//否则，找到最近的俩个质数，相减求得结果
bool isPrime(int n)
{
int i;
for(i = 2;i <= (int)sqrt(double(n)); i++)
if((n % i) == 0)
return false;
return true;
}
int main()
{
int n;
int k,m,u=0;
for(int j=2;j<MAX;j++)
{
if(isPrime(j))
x[u++]=j;
}
while(cin>>n&&n!=0)
{
for(int i=0;i<u;i++)
{
if(x[i]==n)
{
cout<<0<<endl;
break;
}
else
{
if(x[i]<n&&x[i+1]>n)
{
cout<<x[i+1]-x[i]<<endl;
break;
}
}
}
}
}
这篇关于Prime Gap的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
