首页 > 专题系列 > Java解POJ > POJ 2689 Prime Distance [解题报告] Java
2013
11-11

POJ 2689 Prime Distance [解题报告] Java

Prime Distance

问题描述 :

The branch of mathematics called number theory is about properties of numbers. One of the areas that has captured the interest of number theoreticians for thousands of years is the question of primality. A prime number is a number that is has no proper factors (it is only evenly divisible by 1 and itself). The first prime numbers are 2,3,5,7 but they quickly become less frequent. One of the interesting questions is how dense they are in various ranges. Adjacent primes are two numbers that are both primes, but there are no other prime numbers between the adjacent primes. For example, 2,3 are the only adjacent primes that are also adjacent numbers.

Your program is given 2 numbers: L and U (1<=L< U<=2,147,483,647), and you are to find the two adjacent primes C1 and C2 (L<=C1< C2<=U) that are closest (i.e. C2-C1 is the minimum). If there are other pairs that are the same distance apart, use the first pair. You are also to find the two adjacent primes D1 and D2 (L<=D1< D2<=U) where D1 and D2 are as distant from each other as possible (again choosing the first pair if there is a tie).

输入:

Each line of input will contain two positive integers, L and U, with L < U. The difference between L and U will not exceed 1,000,000.

输出:

For each L and U, the output will either be the statement that there are no adjacent primes (because there are less than two primes between the two given numbers) or a line giving the two pairs of adjacent primes.

样例输入:

2 17
14 17

样例输出:

2,3 are closest, 7,11 are most distant.
There are no adjacent primes.

解题代码:

import java.util.Scanner;

 public class Main {

     final static int MAXVALUE = (int) Math.sqrt(Integer.MAX_VALUE) + 1;

     public static void main(String[] args) {
         int k, l, u, tt, index;
         boolean hasFlg;
         int a, b, aa, bb;
         int[] num = new int[MAXVALUE];
         boolean[] frimeflg = new boolean[MAXVALUE];
         boolean[] flg;
         index = 1;
         // ������绔存����缁辩����?
         for (int i = 2; i < MAXVALUE; i++) {
             if (!frimeflg[i]) {
                 k = i * 2;
                 num[index++] = i;
                 while (k < MAXVALUE) {
                     frimeflg[k] = true;
                     k += i;
                 }
             }
         }
         Scanner scan = new Scanner(System.in);
         while (scan.hasNextInt()) {
             l = scan.nextInt();
             u = scan.nextInt();
             tt = (int) Math.sqrt(u);
             // ������绔存���l+1�ㄥ�灏��?
             flg = new boolean[u - l + 1];
             // 缁�盯���灏��杈剧�娑��妲哥槐�虫��ㄥ��g�棰��true
             for (int i = 1; i < index && i <= tt; i++) {
                 k = Math.max(num[i], l / num[i]);
                 if (k * num[i] < l || k <= 1) {
                     k++;
                 }
                 if (k <= 1) {
                     k++;
                 }
                 while ((long) k * num[i] <= u) {
                     flg[k * num[i] - l] = true;
                     k++;
                 }
             }
             hasFlg = false;
             a = 0;
             b = Integer.MAX_VALUE;
             aa = 0;
             bb = 0;
             if (l == 1) {
                 flg[0] = true;
             }
             for (int i = 0; i < u - l + 1; i++) {
                 if (!flg[i]) {
                     for (int j = i + 1; j <= u - l; j++) {
                         if (!flg[j]) {
                             if (b - a > j - i) {
                                 a = i + l;
                                 b = j + l;
                             }
                             if (bb - aa < j - i) {
                                 bb = j + l;
                                 aa = i + l;
                             }
                             hasFlg = true;
                             break;
                         }
                     }
                 }
             }
             if (hasFlg) {
                 System.out.printf(
                         "%d,%d are closest, %d,%d are most distant.\n", a, b,
                         aa, bb);
             } else {
                 System.out.println("There are no adjacent primes.");
             }
         }
     } 
}

  1. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  3. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  4. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

  5. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience