poj 3518 Prime Gap
Time Limit: 5000MS | Memory Limit: 65536K | |
Total Submissions: 7392 | Accepted: 4291 |
Description
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.
Input
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.
Output
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.
Sample Input
10
11
27
2
492170
0
Sample Output
4
0
6
0
114
Source
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
#define maxn 1300000
bool hash[maxn];
void inithash()
{
int i,j;
for(j=; j<maxn; j+=)
hash[j]=;
for(i=; i<; i+=)
if(!hash[i])
for(j=i*i; j<maxn; j+=i)
hash[j]=;
}
int isprime(int N)
{
if(!hash[N])
return true;
return false;
}
int main()
{
inithash();
int n;
while(scanf("%d",&n),n)
{
int i=n;
while()
{
if(isprime(i))
break;
i++;
}
int j=n;
while()
{
if(isprime(j))
break;
j--; }
printf("%d\n",i-j);
}
return ;
}
最新文章
- Angularjs做的一个小页面
- 为公司无线网络启用802.1x协议
- html --- canvas --- javascript --- 绘图方法
- Ext combox 动态 检索
- CodeChef November Challenge 2014
- mirantis fuel
- xargs命令详解
- Python闭包及其作用域
- IOS学习——iphone X的适配
- replace into 浅析之一
- vb代码之-------当窗体BorderStyle属性为0时,添加窗口预览到任务栏
- 开启mysql-binlog日志操作步骤
- 也说Socket
- 创建安全客户端Socket
- Logging - MVC Using Log4net Save to File and Database
- 学习实践之DEMO《nodejs模拟POST登陆》
- how-to-view-source-of-chrome-extension
- 使用dom4j解析xml为json对象
- Linux学习笔记-文件处理和权限命令
- 夜神模拟器调试android studio项目