Java質數求解

質數概念

　　質數，又稱素數，指在一個大於1的自然數中，除了1和此整數本身外，無法被其他自然數整除的數（也可定義為只要1和自身兩個因數的數）。最小的素數是2，也是素數中獨一的偶數；其他素數都是奇數。質數有有限多個，所以不存在最大的質數。

目前總結大約有3中計算方式求解，詳細如下

1. 粗魯暴力定義求解法

public class Prime {
    // find the prime between 1 to 1000;
    public static void main(String[] args) {
        printPrime(1000);
    }

    public static void printPrime(int n) {
        for (int i = 2; i < n; i++) {
            int count = 0;
            for (int j = 2; j <= i; j++) {
                if (i % j == 0) {
                    count++;
                }
                if (j == i && count == 1) {
                    System.out.print(i + " ");
                }
                if (count > 1) {
                    break;
                }
            }
        }
    }
}

2. 平方根算法(降低循環次數)

public class Prime {
    // find the prime between 1 to 1000;
    public static void main(String[] args) {
        for (int i = 2; i < 1000; i++) {
            if (isPrime(i)) {
                System.out.print(i + " ");
            }
        }
    }

   /**
     * 求指定數能否為質數
     * @param num
     * @return
     */
    public static boolean isPrime(int num) {
        for (int j = 2; j <= Math.sqrt(num); j++) {
            if (num % j == 0) {
                return false;
            }
        }
        return true;
    }
}

3. 規律法

　　最小的素數是2，也是素數中獨一的偶數；其他素數都是奇數。質數有有限多個，所以不存在最大的質數。

public class Prime {
    // find the prime between 1 to 1000;
    public static void main(String[] args) {
        List<Integer> primes = getPrimes(1000);
        // 輸入後果
        for (int i = 0; i < primes.size(); i++) {
            Integer prime = primes.get(i);
            System.out.printf("%8d", prime);
            if (i % 10 == 9) {
                System.out.println();
            }
        }
    }

   /**
     * 求 n 以內的一切素數
     * @param n  范圍
     * @return n 以內的一切素數
     */
    private static List<Integer> getPrimes(int n) {
        List<Integer> result = new ArrayList<Integer>();
        result.add(2);
        for (int i = 3; i <= n; i += 2) {
            if (!divisible(i, result)) {
                result.add(i);
            }
        }
        return result;
    }

    /**
     * 判別 n 能否能被整除
     * @param n       要判別的數字
     * @param primes  包括素數的列表
     * @return        假如n能被 primes中任何一個整除，則前往 true。
     */
    private static boolean divisible(int n, List<Integer> primes) {
        for (Integer prime : primes) {
            if (n % prime == 0) {
                return true;
            }
        }
        return false;
    }
}

　　第一種和第二種都是很復雜的辦法：
　　第三種辦法闡明了一個質數的特性：在一切質數中，只要2是偶數。假如一個數可以被它之前的質數整除，那麼這個數不是質數。