poj3518（Prime Gap）

【题意简述】输入一个整数，输出这个整数相邻的2个素数之间的长度，若该整数本身就是素数，则直接输出0。
【分析】素数选择法。

import java.util.*;

import java.io.*;

public class poj_3518{

public static void main(String rgs[]) throws Exception

{

boolean[] prime=new boolean[1299710];

Arrays.fill(prime,true);

prime[1] = false;

prime[0] = false;

for(int i=2; i<=10000; ++i){

if(prime[i])

for (int j=i; i*j<1299710; ++j)

prime[i*j] = false;

}

int n, left, right;

Scanner cin = new Scanner(new BufferedInputStream(System.in));

n = cin.nextInt();

while(n!=0){

if(prime[n])

System.out.println(0);

else{

right = left = n;

while(!prime[--left]);

while(!prime[++right]);

System.out.println(right - left);

}

n = cin.nextInt();

}

posted on 2009-09-02 15:20 飞翔天使阅读(504) 评论(0) 编辑收藏所属分类: poj

随笔分类(146)


只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻知识库 C++博客博问管理
相关文章: poj1157（LITTLE SHOP OF FLOWERS） poj1396（Simple Arithmetics） poj ACM题型分类 poj1125（Stockbroker Grapevine） poj1835（宇航员） poj1163（The Triangle） poj1118（Lining Up） poj1129（Channel Allocation） poj1016（Numbers That Count） poj1001（Exponentiation）