首页 > 专题系列 > Java解POJ > POJ 3518 Prime Gap [解题报告] Java
2013
11-12

POJ 3518 Prime Gap [解题报告] Java

Prime Gap

问题描述 :

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

解题代码:

//* @author popop0p0popo
import java.util.*;
import java.io.*;

public class Main{
    
    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();
        }
    }
}

  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  3. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }