題目描述

您將會得到一個Solution類別和一個main方法,您必須要建立一個Prime類別,並在Prime類別之中實作一個checkPrime方法,讓程式可以正確地輸出質數。



原題網址

https://www.hackerrank.com/challenges/prime-checker

輸入格式

共有五行輸入,每一行輸入包含一個整數。

輸出格式

共有四行輸出,每第n行輸出包含所有大於等於第一行輸入且小於等於第n + 1行輸入整數的質數。

範例輸入

2
1
3
4
5

範例輸出

2
2
2 3
2 3 5

解題概念

由於題目會需要進行4次在一個範圍內搜尋質數的動作,因此我們一開始如果就先建好一個適當範圍的質數表,之後遇到符合範圍內的數字只要查表就可以知道該數字是否為質數,不符合範圍的數字再去計算是否為質數,如此一來程式的執行時間會大大縮減。

至於要判斷一個數字是否為質數,那就要找出大於等於2或小於自己本身的數字範圍中,有沒有哪個數字可以整除自己,如果都沒有的話就代表自己本身就是質數。然而事實上,單純使用這種方式進行質數判斷,效率是很差的,比如要判斷10000是否為質數,豈不是要把2、3、4、5、… 、9999都拿來除看看10000測試是否能整除?若是能使用以下兩種方式來篩選除數,就能大大減少判斷質數的速度:

  • 把要拿來測試的除數分為單數和偶數兩個部份的話,偶數只需拿「2」來測試即可,因為能整除以「4」、「6」、「8」等等偶數的數必定也能整除以「2」。
  • 最大的除數只需取到被除數開根號的無條件捨棄值即可,因為如果有大於或等於這個值的數可以整除被除數,必定又有小於或等於這個值的數可以整除被除數。

那麼質數表該如何建立呢?其實觀察所有質數可以發現,質數必定為6n+1或是6n-1(6的倍數加1或減1),所以只要從中找出質數即可。質數必定為6n+1或是6n-1的證明如下:

若使用6n、6n+1、6n+2、6n+3、6n+4、6n+5來表示所有整數,6n必可用「6」整除和「2」整除,6n+2和6n+4必可用「2」來整除,6n+3=3(2n+1)必可用「3」來整除,所以質數只能是6n+1或是6n+5,而6n+5也可以表示為6(n+1)-1、6n-1。

把沒有必要拿來測試是否為質數的數字先排除掉,如此一來質數表的建立就會快上好幾倍!

參考答案

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.reflect.Method;
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

import static java.lang.System.in;

class Prime {

    private static final int MAX_PRIME_TABLE = 10000;
    private static final TreeSet<Integer> primeTable = new TreeSet<>();

    static {
        primeTable.add(2);
        primeTable.add(3);
        for (int i = 1; i <= MAX_PRIME_TABLE; i += 6) { 
            final int i6 = i * 6;
            final int a = i6 - 1;
            final int b = i6 + 1;
            if (isPrime(a)) {
                primeTable.add(a);
            }
            if (isPrime(b)) {
                primeTable.add(b);
            }
        }
    }

    private static boolean isPrime(final int n) {
        if (n % 2 == 0) {
            return false;
        }
        final int sqrtN = (int) Math.sqrt(n);
        for (int i = 3; i <= sqrtN; i += 2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public void checkPrime(final int... n) {
        final StringBuilder sb = new StringBuilder();
        final int length = n.length;
        for (int i = 0; i < length; ++i) {
            final int number = n[i];
            boolean isPrime = false;
            if (number > MAX_PRIME_TABLE) {
                final int m = number % 6;
                isPrime = (m == 1 || m == 5) && isPrime(number);
            } else {
                isPrime = primeTable.contains(number);
            }

            if (isPrime) {
                sb.append(number).append(' ');
            }
        }
        System.out.println(sb.toString().trim());
    }
}

public class Solution {

    public static void main(final String[] args) throws Exception {
        try {
            final BufferedReader br = new BufferedReader(new InputStreamReader(in));
            final int n1 = Integer.parseInt(br.readLine());
            final int n2 = Integer.parseInt(br.readLine());
            final int n3 = Integer.parseInt(br.readLine());
            final int n4 = Integer.parseInt(br.readLine());
            final int n5 = Integer.parseInt(br.readLine());
            final Prime ob = new Prime();
            ob.checkPrime(n1);
            ob.checkPrime(n1, n2);
            ob.checkPrime(n1, n2, n3);
            ob.checkPrime(n1, n2, n3, n4, n5);
            final Method[] methods = Prime.class.getDeclaredMethods();
            final Set<String> set = new HashSet<>();
            boolean overload = false;
            for (int i = 0; i < methods.length; i++) {
                if (set.contains(methods[i].getName())) {
                    overload = true;
                    break;
                }
                set.add(methods[i].getName());

            }
            if (overload) {
                throw new Exception("Overloading not allowed");
            }
        } catch (Exception e) {
            System.out.println(e);
        }
    }
}