素數演算法（Prime Num Algorithm）

數學是科學的皇后，而素數可以說是數學最為核心的概念之一，圍繞素數產生了很多偉大的故事，最為著名莫過于哥德巴赫猜想、素數定理和黎曼猜想（有趣的是，自牛頓以來的三個最偉大數學家，歐拉、高斯和黎曼，分別跟這些問題有著深刻的淵源），我寫這篇文章不是要探討和解決這些偉大猜想和定理，而是回歸問題本身，用計算機判定一個素數，以及求取特定正整數值下所包含的所有素數，這篇文章，算是自己對素數問題思考的一次總結，

先說一下素數的定義：

素數也叫質數，是只能被 \(1\) 和其本身所能整除的非\(1\)正整數，

第一個素數是2，它也是唯一一個偶素數，100以內素數列為：

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

有了素數的定義，我們通過計算機程式來解決以下問題，

給定一個正整數\(n\), 判定該數是否為素數，
給定一個正整數\(n\), 求取小于等于該數的所有素數列，
給定兩個正整數 \(n_1\), \(n_2\)(\(n_1 \le n_2\))，求取 \(n_1\)到 \(n_2\)之間其所包含的素數列，
從\(2\)開始計算大素數，

解決上述問題的核心演算法都是埃拉托斯特尼篩法,簡稱埃氏篩選法，這個方法的內容即每當我們得到一個素數后，我們即將這個素數的所有倍數（\(2\)倍以上）的整數洗掉，重復執行該程序，最后余下來的一定是素數，

1. 給定一個正整數\(n\), 判定該數是否為素數

1.1 初始演算法

1.1.1 演算法

判定一個整數\(n\)是否為素數，我們只需要判定該整數是否不能被小于它的非\(1\)整數所整除，

1.1.2 代碼

package com.lunyu.algorithm.math.numberTheory;

import com.google.common.collect.Lists;
import java.util.List;

/**
 * 求素數演算法
 * @author lunyu
 * @since 2022/7/14
 */
public class PrimeNumMain {

    public static void main(String[] args) {
        // 盧卡斯數列
        List<Integer> nums = Lists.newArrayList(1, 3, 4, 7, 11, 18, 29, 47, 76, 123);
        for (Integer num : nums) {
            boolean isPrime = isPrime(num);
            System.out.println("整數：" + num + "是否為素數：" + isPrime);
        }
    }

    /**
   * 給定一個正整數n, 判定該數是否為素數
   */
    private static boolean isPrime(int num){

        if (1 >= num){
            return false;
        }

        for (int i = 2; i < num; i++){
            if (0 == num % i){
                return false;
            }
        }
        return true;
    }
}

1.1.3 演算法復雜度

時間復雜度	空間復雜度
\(O(n)\)	\(O(1)\)

1.2 演算法優化1

因為\(2\)是唯一的一個偶素數，因此，我們可以在判定時將\(2\)的情況特殊處理，并且每次只需判定小于該數的奇數的情況，

1.2.1 演算法

判定一個整數\(n\)是否為素數，我們只需要判定

該數是是否是\(2\)，
在該數不為\(2\)的情形下，該數是否不被\(2\)或小于它的非\(1\)奇數所整除，

1.2.2 代碼

/**
   * 經過優化的給定一個正整數n, 判定該數是否為素數
   */
private static boolean isPrimeOptimized1(int num){
 
    if (1 >= num){
        return false;
    }
    // 判定是否等于2
    if (2 == num){
        return true;
    }
    // 判定能否被2整除
    if (0 == num % 2){
        return false;
    }
    // 判定能否能被小于自身且大于等于3的奇數整除
    for (int i = 3; i < num;){
        if (0 == num % i){
            return false;
        }
        i += 2;
    }
    return true;
}

1.2.3 演算法復雜度

時間復雜度	空間復雜度
\(O(\frac{n}{2})\)	\(O(1)\)

1.3 演算法優化2

實際上，判定一個整數\(n\)是否為素數，我們可以縮減判定的范圍，將之前的全量比較，變更為，判定該整數是否不能被其開方后的整數向下取整（\(\lfloor \sqrt{n} \rfloor\)）以內（含\(\lfloor \sqrt{n} \rfloor\)）的非\(1\)整數所整除，

直觀一點，即自然數\(n\)，能否不被整數列集合\(\{x| 2\le x\le \lfloor \sqrt{n} \rfloor, x\in Z_+\}\)所整除，

這個優化判定是可以證明的，我們來給出證明，

1.3.1 證明

設有正整數\(n\),它不能被其開方后的整數向下取整（\(\lfloor \sqrt{n} \rfloor\)）以內（含\(\lfloor \sqrt{n} \rfloor\)）的非\(1\)整數所整除，我們證明它一定是一個素數，

我們用反證法，

假設它是一個合數，那么它一定可以表示成兩個非\(1\)整數\(z_1 \cdot z_2\)乘積的形式，

我們又已知，它不能被其開方后的整數向下取整（\(\lfloor \sqrt{n} \rfloor\)）以內（含\(\lfloor \sqrt{n} \rfloor\)）的非\(1\)整數所整除，因此無論是\(z_1\)還是\(z_2\)，都不可能包含\(1\)到\(\lfloor \sqrt{n} \rfloor\)之間的素因子，否則與\(n\)不能被1到（\(\lfloor \sqrt{n} \rfloor\)）的非\(1\)整數所整除矛盾，

于是，無論是\(z_1\)還是\(z_2\)都必包含大于\(\lfloor \sqrt{n} \rfloor\)的素因子，這兩個素因子分別記作\(\lfloor \sqrt{n} \rfloor + k_1\),\(\lfloor \sqrt{n} \rfloor + k_2\)（\(k_1,k_2 \ge 1\)），

于是,

\[\begin{align} z_1 \cdot z_2 &\ge (\lfloor \sqrt{n} \rfloor + k_1)(\lfloor \sqrt{n} \rfloor + k_2) \\ & \ge (\lfloor \sqrt{n} \rfloor + 1)(\lfloor \sqrt{n} \rfloor + 1) \\ & = (\lfloor \sqrt{n} \rfloor + 1)^2 \\ & > n \end{align} \]

為什么\((\lfloor \sqrt{n} \rfloor + 1)^2 \gt n\)，因為\(\lfloor \sqrt{n} \rfloor + 1 > \sqrt{n}\)，這里將\(\sqrt{n}\)取值為任意一正實數\(r\)，我們可以得知任意正實數\(r\)的向下取整\(\lfloor r \rfloor\)滿足：

\[\left\{ \begin{aligned} \lfloor r \rfloor & = r & , if \ r \in Z_+ \\ \lfloor r \rfloor & \gt r-1 & , if\ r \notin Z_+ \end{aligned} \right. \]

于是，

\[\left\{ \begin{aligned} \lfloor r \rfloor + 1 = r + 1 & \gt r & , if \ r \in Z_+ \\ \lfloor r \rfloor + 1 \gt (r-1) + 1 & = r & , if\ r \notin Z_+ \end{aligned} \right. \]

證畢，

1.3.2 演算法

判定一個整數\(n\)是否為素數，只需判定該整數是否不能被其開方后的整數向下取整（\(\lfloor \sqrt{n} \rfloor\)）以內（含\(\lfloor \sqrt{n} \rfloor\)）的非\(1\)整數所整除，

1.3.3 代碼

/**
   * 經過優化的給定一個正整數n, 判定該數是否為素數
   */
private static boolean isPrimeOptimized2(int num){

    if (1 >= num){
      return false;
    }
    // 整數num開方向下取整
    double sqrtFloorNum = Math.floor(Math.sqrt(num));
    for (int i = 2; i <= sqrtFloorNum; i++){
        if (0 == num % i){
            return false;
        }
    }
    return true;
}

1.3.4 演算法復雜度

時間復雜度	空間復雜度
\(O(n^{\frac{1}{2}})\)	\(O(1)\)

1.4 演算法優化結合

我們可以將1.2 演算法優化1和1.3 演算法優化2結合起來，形成一個更優演算法，

1.4.1 演算法

判定一個整數\(n\)是否為素數，我們只需要判定

該數是是否是\(2\)，
在該數不為\(2\)的情形下，該數是否不被以下數所整除：
- 不被\(2\)整除，
- 不被其開方后的整數向下取整（\(\lfloor \sqrt{n} \rfloor\)）以內（含\(\lfloor \sqrt{n} \rfloor\)）的非\(1\)奇數所整除，

1.4.2 代碼

/**
 * 給定一個正整數n, 判定該數是否為素數
 */
private static boolean isPrimeOptimized3(int num){

    if (1 >= num){
        return false;
    }
    if (2 == num){
        return true;
    }
    if (0 == num % 2){
        return false;
    }
    // 整數num開方向下取整
    double sqrtFloorNum = Math.floor(Math.sqrt(num));
    for (int i = 3; i <= sqrtFloorNum;){
        if (0 == num % i){
            return false;
        }
        i += 2;
    }
    return true;
}

1.4.3 演算法復雜度

時間復雜度	空間復雜度
\(O(\frac{1}{2} n^{\frac{1}{2}})\)	\(O(1)\)

2. 給定一個正整數\(n\), 求取小于等于該數的所有素數列

易知，該問題即是上一問題的序列化，也即將上一問題在外層再套一層for回圈，平鋪展開后的問題，

于是，我們先給出一個初始演算法，

2.1 初始演算法

2.1.1 演算法

給定一個正整數\(n\), 求取小于等于該數的所有素數列, 即

對從\(2\)到\(n\)的每一個整數，我們依次判定該數是否為素數，如果為素數，我們將該數存盤起來得到的素數列，

2.1.2 代碼

package com.lunyu.algorithm.math.numberTheory;

import java.util.ArrayList;
import java.util.List;

/**
 * 求素數演算法
 * @author lunyu
 * @since 2022/7/14
 */
public class PrimeNumMain {

    public static void main(String[] args) {
        int n = 300;

        List<Integer> primeNums = new ArrayList<>();
        getPrimeNums(n, primeNums);

        // TODO: 結果輸出
        System.out.println(n + "以內的素數為：");
        for (Integer primeNum : primeNums) {
            System.out.print(primeNum + " ");
        }

    }

    /**
   * 獲得n以內（含n）的素數列
   * @param n
   * @param primeNums
   */
    private static void getPrimeNums(int n, List<Integer> primeNums) {
        for (int i = 2; i <= n; i++){
            boolean isPrime = isPrime(i);
            if (isPrime){
                primeNums.add(i);
            }
        }
    }

    /**
    * 給定一個正整數n, 判定該數是否為素數
    */
    private static boolean isPrime(int num){

        if (1 >= num){
            return false;
        }

        for (int i = 2; i < num; i++){
            if (0 == num % i){
                return false;
            }
        }
        return true;
    }
}

2.1.3 演算法復雜度

因為多了外層的一層for回圈，而內層判定一個整數是否為素數的演算法我們用的初始演算法(isPrime(int num))，因此其時間復雜度為\(O(n \cdot n)\)也即\(O(n^2)\)，

而空間復雜度，因為我們有素數列的采集動作，因此這里空間復雜度不是\(O(1)\)，而是\(O(n/{\ln n})\)，這里的值取自素數定理，即一個自然數\(x\)以內的素數個數\(\pi(x)\)，其漸進估計為\(\pi(x) \sim x/\ln x\)，

時間復雜度	空間復雜度
\(O(n^2)\)	\(O(n/{\ln n})\)

2.2 演算法優化1

這里演算法優化我們分為2部分，第一部分是判定單個整數是否素數的優化；第2部分，我們對外層回圈進行優化，

第一部分，我們取章節1.4 演算法優化結合給出最終優化方案，

第二部分，我們對for回圈內的資料進行一次簡單優化，同樣易知，\(n\)以內的素數除\(2\)意外都是奇素數，因此這里我們可以將外層for回圈判定的資料也減半，

2.2.1 演算法

給定一個正整數\(n\), 求取小于等于該數的所有素數列, 即

對\(2\)和從\(3\)到\(n\)的每一個奇數，我們依次判定該數是否為素數 (判定該數是否為素數，取自1.4.1 演算法優化結合-演算法)，

如果為素數，我們將該數存盤起來得到的素數列，

2.2.2 代碼

public static void main(String[] args) {
    int n = 300;

    List<Integer> primeNums = new ArrayList<>();
    getPrimeNumsOptimized1(n, primeNums);

    // TODO: 結果輸出
    System.out.println(n + "以內的素數為：");
    for (Integer primeNum : primeNums) {
        System.out.print(primeNum + " ");
    }

}

/**
 * 獲得n以內（含n）的素數列
 * @param n
 * @param primeNums
 */
private static void getPrimeNumsOptimized1(int n, List<Integer> primeNums) {
    if (1 >= n){
        return;
    }
    // 如果n >= 2, 則n以內的素數默認含有2
    primeNums.add(2);
    // 對大于等3的奇數判定
    for (int i = 3; i <= n;){
        boolean isPrime = isPrimeOptimized3(i);
        if (isPrime){
            primeNums.add(i);
        }
        i += 2;
    }
}

/**
 * 給定一個正整數n, 判定該數是否為素數
 */
private static boolean isPrimeOptimized3(int num){

    if (1 >= num){
        return false;
    }
    if (2 == num){
        return true;
    }
    if (0 == num % 2){
        return false;
    }
    // 整數num開方向下取整
    double sqrtFloorNum = Math.floor(Math.sqrt(num));
    for (int i = 3; i <= sqrtFloorNum;){
        if (0 == num % i){
            return false;
        }
        i += 2;
    }
    return true;
}

這里外回圈針對的是大于等于\(3\)的奇數，因此，內層方法判斷該數小于等于\(1\) 、是否等于\(2\)和是否能被\(2\)整除的判定就顯得多余了，這里可以刪掉，變更為

public static void main(String[] args) {
    int n = 300;

    List<Integer> primeNums = new ArrayList<>();
    getPrimeNumsOptimized1(n, primeNums);

    // TODO: 結果輸出
    System.out.println(n + "以內的素數為：");
    for (Integer primeNum : primeNums) {
        System.out.print(primeNum + " ");
    }

}

/**
 * 獲得n以內（含n）的素數列
 * @param n
 * @param primeNums
 */
private static void getPrimeNumsOptimized1(int n, List<Integer> primeNums) {
    if (1 >= n){
        return;
    }
    // 如果n >= 2, 則n以內的素數默認含有2
    primeNums.add(2);
    // 對大于等3的奇數判定
    for (int i = 3; i <= n;){
        boolean isPrime = isPrimeOptimized3(i);
        if (isPrime){
            primeNums.add(i);
        }
        i += 2;
    }
}

/**
 * 給定一個大于等于3的奇數n, 判定該數是否為素數
 */
private static boolean isPrimeOptimized3(int num){
    
    // 整數num開方向下取整
    double sqrtFloorNum = Math.floor(Math.sqrt(num));
    for (int i = 3; i <= sqrtFloorNum;){
        if (0 == num % i){
            return false;
        }
        i += 2;
    }
    return true;
}

2.2.3 演算法復雜度

易知外層的for回圈其時間復雜度為\(O(\frac{1}{2}n)\),內層時間復雜度為\(O(\frac{1}{2} n^{\frac{1}{2}})\)，因此總的時間復雜度為\(O(\frac{1}{4} n^{\frac{3}{2}})\)，

空間復雜度不變，仍為\(O(n/{\ln n})\)，

時間復雜度	空間復雜度
\(O(\frac{1}{4} n^{\frac{3}{2}})\)	\(O(n/{\ln n})\)

2.3 演算法優化2

1.3 演算法優化2中，判定一個整數是否為素數，即判定該數是否不能被其開方后的整數向下取整（\(\lfloor \sqrt{n} \rfloor\)）以內（含\(\lfloor \sqrt{n} \rfloor\)）的非\(1\)整數所整除，

這個地方的判定，我們可以進一步優化為，判定一個整數是否為素數，即判定該數是否不能被其開方后的整數向下取整（\(\lfloor \sqrt{n} \rfloor\)）以內（含\(\lfloor \sqrt{n} \rfloor\)）的非\(1\)素數所整除，

直觀一點，即自然數\(n\)，能否不被素數列集合\(\{x| 2\le x\le \lfloor \sqrt{n} \rfloor, x\in P_+\}\)所整除，

證明略，同1.3.1 演算法優化2-證明，

有了以上優化點，我們還缺少素數列集合\(\{x| 2\le x\le \lfloor \sqrt{n} \rfloor, x\in P_+\}\)，幸運的是，我們的目標“給定一個正整數\(n\), 求取小于等于該數的所有素數列”即隱含的包含該資訊，也即殊途同歸，目標基本一致，有了這些條件，我們就可以對2.1 初始演算法進行一定的優化，

2.3.1 演算法

給定一個正整數\(n\), 求取小于等于該數的所有素數列, 即

對從\(2\)到\(n\)的每一個整數，我們依次判定該數是否為素數，如果為素數，我們將該數存盤起來得到的素數列，

判定是否為素數的法則為，該數能否不被素數列集合\(\{x| 2\le x\le \lfloor \sqrt{n} \rfloor, x\in P_+\}\)所整除，

素數列集合\(\{x| 2\le x\le \lfloor \sqrt{n} \rfloor, x\in P_+\}\)，在計算程序中得到，

2.3.2 代碼

package com.lunyu.algorithm.math.numberTheory;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 求素數演算法
 * @author lunyu
 * @since 2022/7/14
 */
public class PrimeNumMain {

    public static void main(String[] args) {
        int n = 300;

        List<Integer> primeNums = new ArrayList<>();
        getPrimeNumsOptimized2(n, primeNums);

        // TODO: 結果輸出
        System.out.println(n + "以內的素數為：");
        for (Integer primeNum : primeNums) {
            System.out.print(primeNum + " ");
        }

    }

    /**
     * 獲得n以內（含n）的素數列
     * @param n
     * @param primeNums
     */
    private static void getPrimeNumsOptimized2(int n, List<Integer> primeNums) {

        if (1 >= n){
            return;
        }

        for (int i = 2; i <= n; i++){
            boolean isPrime = isPrimeOptimized4(i, primeNums);
            if (isPrime){
                primeNums.add(i);
            }
        }

    }

    /**
     *  判定是否為素數
     */
    private static boolean isPrimeOptimized4(int num, List<Integer> primeNums) {

        if (1 >= num){
            return false;
        }
        // 整數num開方向下取整
        double sqrtFloorNum = Math.floor(Math.sqrt(num));

        // 判定能否被素數列整數
        for (Integer primeNum : primeNums) {
            if (primeNum > sqrtFloorNum){
                break;
            }
            if (0 == num % primeNum){
                return false;
            }
        }

        return true;
    }
}

這里外回圈針對的是大于等于\(3\)的奇數，因此，內層方法判斷該數小于等于\(1\) 就顯得多余了，這里可以刪掉，變更為

 /**
  *  判定是否為素數
  */
private static boolean isPrimeOptimized4(int num, List<Integer> primeNums) {

    // 整數num開方向下取整
    double sqrtFloorNum = Math.floor(Math.sqrt(num));

    for (Integer primeNum : primeNums) {
        if (primeNum > sqrtFloorNum){
            break;
        }
        if (0 == num % primeNum){
            return false;
        }
    }

    return true;
}

2.3.3 演算法復雜度

易知，外層的for回圈其時間復雜度為\(O(n)\)；內層, 遍歷素數列集合\(\{x| 2\le x\le \lfloor \sqrt{n} \rfloor, x\in P_+\}\)的時間復雜度為\(O(n^{\frac{1}{2}}/\ln n^{\frac{1}{2}}) = O(\frac{1}{2}n^{\frac{1}{2}}/\ln n)\),因此總的時間復雜度為\(O(\frac{1}{2}n^{\frac{3}{2}}/\ln n)\)，

獲得素數列，其空間復雜度為\(O(n/{\ln n})\)，

時間復雜度	空間復雜度
\(O(\frac{1}{2}n^{\frac{3}{2}}/\ln n)\)	\(O(n /\ln n)\)

2.4 演算法優化結合

我們可以將2.2 演算法優化1和2.3 演算法優化2結合起來，形成一個更優演算法，

2.4.1 演算法

給定一個正整數\(n\), 求取小于等于該數的所有素數列, 即

對\(2\)和從\(3\)到\(n\)的每一個奇數，我們依次判定該數是否為素數 (判定該數是否為素數，取自2.3.1 演算法優化2-演算法)，

如果為素數，我們將該數存盤起來得到的素數列，

2.4.2 代碼

package com.lunyu.algorithm.math.numberTheory;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 求素數演算法
 * @author lunyu
 * @since 2022/7/14
 */
public class PrimeNumMain {

    public static void main(String[] args) {
        int n = 300;

        List<Integer> primeNums = new ArrayList<>();
        getPrimeNumsOptimized4(n, primeNums);

        // TODO: 結果輸出
        System.out.println(n + "以內的素數為：");
        for (Integer primeNum : primeNums) {
            System.out.print(primeNum + " ");
        }

    }

    /**
     * 獲得n以內（含n）的素數列
     * @param n
     * @param primeNums
     */
    private static void getPrimeNumsOptimized4(int n, List<Integer> primeNums) {
        if (1 >= n){
            return;
        }
        // 如果n >= 2, 則n以內的素數默認含有2
        primeNums.add(2);
        // 對大于等3的奇數判定
        for (int i = 3; i <= n;){
            boolean isPrime = isPrimeOptimized4(i, primeNums);
            if (isPrime){
                primeNums.add(i);
            }
            i += 2;
        }
    }

    /**
     *  判定是否為素數
     */
    private static boolean isPrimeOptimized4(int num, List<Integer> primeNums) {

        // 整數num開方向下取整
        double sqrtFloorNum = Math.floor(Math.sqrt(num));

        for (Integer primeNum : primeNums) {
            if (primeNum > sqrtFloorNum){
                break;
            }
            if (0 == num % primeNum){
                return false;
            }
        }

        return true;
    }
}

2.4.3 演算法復雜度

易知，外層的for回圈其時間復雜度為\(O(\frac{n}{2})\)；內層, 遍歷素數列集合\(\{x| 2\le x\le \lfloor \sqrt{n} \rfloor, x\in P_+\}\)的時間復雜度為\(O(n^{\frac{1}{2}}/\ln n^{\frac{1}{2}}) = O(\frac{1}{2}n^{\frac{1}{2}}/\ln n)\),因此總的時間復雜度為\(O(\frac{1}{4}n^{\frac{3}{2}}/\ln n)\)，

獲得素數列，其空間復雜度為\(O(n/{\ln n})\)，

時間復雜度	空間復雜度
\(O(\frac{1}{4}n^{\frac{3}{2}}/\ln n)\)	\(O(n/{\ln n})\)

3. 給定兩個正整數 \(n_1\), \(n_2\)(\(n_1 \le n_2\))，求取 \(n_1\)到 \(n_2\)之間其所包含的素數列

這里有兩種方式可以解決問題：

第一種對\(n_1\)到 \(n_2\)之間整數，我們依次判定是否為素數，如果為素數，我們將它們采集起來得到素數列即為所求，

第二種，我們先求出小于等于\(n_2\)的所有素數列，再將該素數列中介于\(n_1\), \(n_2\)的素數列（\(\{x | n_1 \le x \le n_2, x \in P_+ \}\)）取出即為所求，

3.1 演算法1

為了減少篇幅，這里直接使用1.4 演算法優化結合中的演算法，而不從頭開始逐步優化，

3.1.1 演算法

給定兩個正整數 \(n_1\), \(n_2\)(\(n_1 \le n_2\))，求取 \(n_1\)到 \(n_2\)之間其所包含的素數列，即

對\(n_1\)到 \(n_2\)之間整數，我們依次判定是否為素數，如果為素數，我們將它們采集起來得到素數列即為所求，

判定素數演算法為1.4.1 演算法，

3.1.2 代碼

package com.lunyu.algorithm.math.numberTheory;

import java.util.ArrayList;
import java.util.List;

/**
 * 求素數演算法
 * @author lunyu
 * @since 2022/7/14
 */
public class PrimeNumMain {

    public static void main(String[] args) {

        int n1 = 100, n2 = 200;
        List<Integer> primeNums = new ArrayList<>();
        for (int i = n1; i <= n2; i++) {
            boolean isPrime = isPrimeOptimized3(i);
            if (isPrime){
                primeNums.add(i);
            }
        }

        // TODO: 結果輸出
        System.out.println("整數" + n1 +  ", " + n2 + "之間的素數為：");
        for (Integer primeNum : primeNums) {
            System.out.print(primeNum + " ");
        }

    }

    /**
     * 給定一個正整數n, 判定該數是否為素數
     */
    private static boolean isPrimeOptimized3(int num){

        if (1 >= num){
            return false;
        }
        if (2 == num){
            return true;
        }
        if (0 == num % 2){
            return false;
        }
        // 整數num開方向下取整
        double sqrtFloorNum = Math.floor(Math.sqrt(num));
        for (int i = 3; i <= sqrtFloorNum;){
            if (0 == num % i){
                return false;
            }
            i += 2;
        }
        return true;
    }
}

3.1.3 演算法復雜度

易知外層回圈時間復雜度為\(O(n_2-n_1)\)，內層回圈時間復雜度是\(O(\frac{1}{2} n_2^{\frac{1}{2}})\)，于是總的時間復雜度為\(O(\frac{1}{2} n_2^{\frac{1}{2}}(n_2-n_1))\)，

因為有素數列的采集動作，因此這里空間復雜度是\(O(n_2/{\ln n_2} - n_1/{\ln n_1})\)，

時間復雜度	空間復雜度
\(O(\frac{1}{2} n_2^{\frac{1}{2}}(n_2-n_1))\)	\(O(n_2/{\ln n_2} - n_1/{\ln n_1})\)

注：上述演算法還能再進一步優化，在外層回圈中，我們處理好\(n_1\)，\(n_2\)可能存在的\(=2\)這個特殊情況后，其中的回圈變數，只取介于\(n_1\)到\(n_2\)的奇數進行判定，這樣時間復雜度可減半，變為\(O(\frac{1}{4} n_2^{\frac{1}{2}}(n_2-n_1))\)，

3.2 演算法2

同樣為了減少篇幅，我們直接使用2.4 演算法優化結合中的演算法，而不從頭開始逐步優化，

3.2.1 演算法

給定兩個正整數 \(n_1\), \(n_2\)(\(n_1 \le n_2\))，求取 \(n_1\)到 \(n_2\)之間其所包含的素數列，即

先求出小于等于\(n_2\)的所有素數列，再將介于\(n_1\)到 \(n_2\)之間素數取出即為所求，

求出小于等于\(n_2\)的所有素數列演算法取自2.4.1 演算法

3.2.2 代碼

package com.lunyu.algorithm.math.numberTheory;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 求素數演算法
 * @author lunyu
 * @since 2022/7/14
 */
public class PrimeNumMain {

    public static void main(String[] args) {

        int n1 = 100, n2 = 200;
        List<Integer> primeNums = new ArrayList<>();
        getPrimeNumsOptimized2(n2, primeNums);

        primeNums = primeNums.stream().filter(e -> e.intValue() >= n1)
            .collect(Collectors.toList());

        // TODO: 結果輸出
        System.out.println("整數" + n1 +  ", " + n2 + "之間的素數為：");
        for (Integer primeNum : primeNums) {
            System.out.print(primeNum + " ");
        }

    }

    /**
     * 獲得n以內（含n）的素數列
     * @param n
     * @param primeNums
     */
    private static void getPrimeNumsOptimized2(int n, List<Integer> primeNums) {

        if (1 >= n){
            return;
        }
        // 如果n >= 2, 則n以內的素數默認含有2
        primeNums.add(2);
        // 對大于等3的奇數判定
        for (int i = 3; i <= n;){

            if (1 >= n){
                return;
            }

            boolean isPrime = isPrimeOptimized4(i, primeNums);
            if (isPrime){
                primeNums.add(i);
            }
            i += 2;
        }
    }

    /**
     *  判定是否為素數
     */
    private static boolean isPrimeOptimized4(int num, List<Integer> primeNums) {

        // 整數num開方向下取整
        double sqrtFloorNum = Math.floor(Math.sqrt(num));

        for (Integer primeNum : primeNums) {
            if (primeNum > sqrtFloorNum){
                break;
            }
            if (0 == num % primeNum){
                return false;
            }
        }

        return true;
    }

}

3.2.3 演算法復雜度

易知，外層的for回圈其時間復雜度為\(O(\frac{n_2}{2})\)；內層, 遍歷素數列集合\(\{x| 2\le x\le \lfloor \sqrt{n} \rfloor, x\in P_+\}\)的時間復雜度為\(O(n_2^{\frac{1}{2}}/\ln n_2^{\frac{1}{2}}) = O(\frac{1}{2}n_2^{\frac{1}{2}}/\ln n_2)\),因此總的時間復雜度為\(O(\frac{1}{4}n_2^{\frac{3}{2}}/\ln n_2)\)，

獲得素數列，其空間復雜度為\(O(n_2/{\ln n_2})\)，獲得介于 \(n_1\), \(n_2\)的素數列，其空間復雜度為\(O(n_2/{\ln n_2} - n_1/{\ln n_1})\)，于是總的空間復雜度為\(O(2n_2/{\ln n_2} - n_1/{\ln n_1})\)，

時間復雜度	空間復雜度
\(O(\frac{1}{4}n_2^{\frac{3}{2}}/\ln n_2)\)	\(O(2n_2/{\ln n_2} - n_1/{\ln n_1})\)

4. 從\(2\)開始計算大素數

從計算機誕生以來，計算超大素數就成為了可能，目前最大的已知素數為\((2^{82,589,933}-1)\)（來自網路），足有\(2500\)萬位，計算大素數、超大素數可以用來驗證很多有關素數的問題，

本文即從演算法可行的角度，從\(2\)開始來計算大素數，并對計算程序進行一定的優化，

4.1 演算法1

我們怎么計算大素數呢？這里我要反其道而行之，先算一部分，然后再算一部分，最后算到我們想要的數為止，說的太含混了，下面以例子進行說明，

首先，我們先獲取到素數\(2\)，構成初始素數列\(\{2\}\)，我們取其中最大的素數，即\(2\)，我們知道\(2^2=4\)，于是，我們可以得到大于\(2\)且小于\(2^2\)的奇數列\(\{3\}\) ，我們判定這個數列中不能被初始素數列\(\{2\}\)整除的數，得到數列\(\{3\}\) ，我們將初始素數列\(\{2\}\)和新得到的數列\(\{3\}\)合并得到小于\(4\)的素數列\(\{2,3\}\)，

進行第二次回圈，我們已知初始素數列\(\{2,3\}\)，取其中最大的素數，即\(3\)，我們知道\(3^2=9\)，于是，我們可以得到大于\(3\)且小于\(3^2\)的奇數列\(\{5,7\}\) ，我們判定這個數列中不能被已知初始素數列\(\{2,3\}\)所整除的數，得到數列\(\{5,7\}\)，我們將初始素數列\(\{2,3\}\)和新得到的數列\(\{5,7\}\)合并得到小于\(9\)的素數列\(\{2,3,5,7\}\)，

進行第三次回圈，我們已知初始素數列\(\{2,3,5,7\}\)，取其中最大的素數，即\(7\)，我們知道\(7^2=49\)，于是，我們可以得到大于\(7\)且小于\(7^2\)的奇數列\(\{9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43\}\) ，我們判定這個數列中不能被已知初始素數列\(\{2,3,5,7\}\)所整除的數，得到數列\(\{11,13,17,19,23,29,31,37,41,43\}\)，我們將初始素數列\(\{2,3,5,7\}\)和新得到的數列\(\{11,13,17,19,23,29,31,37,41,43\}\)合并得到小于\(49\)的素數列\(\{2,3,5,7,11,13,17,19,23,29,31,37,41,43\}\)，

以此類推，

我們可以用這種方式，一直計算下去，得到任意的大的素數（如果算力允許的話），

4.1.1 演算法

從\(2\)開始計算大素數即重復執行以下程序，

設全量的初始素數列\(\{2,3,\dots,p_k\}, k \ge 2\)，我們取其中最大的奇素數，即\(p_k\)，我們可以得到大于\(p_k\)且小于\(p_k^2\)的奇數列\(\{p_k + 2,\dots\ , p_k^2 - 2\}\) ，我們判定這個數列中不能被初始素數列\(\{2,\dots,p_k\}, k \ge 2\)整除的數，得到數列\(\{p_{k + 1}, \dots , p_l\}\) ，我們將初始素數列\(\{2,3,\dots,p_k\}, k \ge 2\)和新得到的素數列\(\{p_{k + 1}, \dots , p_l\}\)合并得到小于\(p_k^2\)的素數列\(\{2,3,\dots,p_l\}, l \ge 2\)，

4.1.2 代碼

package com.lunyu.algorithm.math.numberTheory;

import com.google.common.collect.Lists;
import java.util.List;

/**
 * 求素數演算法
 * @author lunyu
 * @since 2022/7/14
 */
public class PrimeNumMain {

    /**
     * 素數上限
     * 我們還是要設定一個上限，以便退出程式
     */
    private static final int PRIME_NUM_LIMIT = 300000;

    public static void main(String[] args) {

        List<Integer> primeNums = Lists.newArrayList(2, 3);
        int round = 1;

        getPrimeNumsByRound(primeNums, round);

        // TODO: 結果輸出
        for (Integer primeNum : primeNums) {
            System.out.print(primeNum + " ");
        }
    }

    /**
     * 按輪次求大素數
     */
    private static void getPrimeNumsByRound(List<Integer> primeNums, int round) {

        // 獲得已知素數列的最后一個素數
        Integer lastPrimeNum = primeNums.get(primeNums.size() - 1);
        // 迭代截止
        if (lastPrimeNum >= PRIME_NUM_LIMIT){
            return;
        }
        System.out.println("執行輪次 round：" + round);

        // 執行演算法
        for (int i = lastPrimeNum + 2; i <= (lastPrimeNum * lastPrimeNum - 2);){
            // 迭代截止
            if (i >= PRIME_NUM_LIMIT){
                return;
            }
            boolean isPrime = isPrime(i, primeNums);
            if (isPrime){
                primeNums.add(i);
            }
            i += 2;
        }

        round ++;
        getPrimeNumsByRound(primeNums, round);
    }

    /**
     *  判定是否為素數
     */
    private static boolean isPrime(int num, List<Integer> primeNums) {

        for (Integer primeNum : primeNums) {
            if (0 == num % primeNum){
                return false;
            }
        }

        return true;
    }

}

4.1.3 演算法復雜度

時間復雜度	空間復雜度
\(O(\frac{1}{4}n^{\frac{3}{2}}/\ln n)\)	\(O(n/{\ln n})\)

注：雖然演算法復雜度沒有變，但是執行時間上，使用遞回的方式還是比回圈的方式慢了不少，我想可能跟遞回成本高有很大關系，

作者：論語
出處：https://www.cnblogs.com/lunyu/p/16495874.html
著作權：本文著作權歸作者和博客園共有
轉載：歡迎轉載，但未經作者同意，必須保留此段宣告；必須在文章中給出原文連接；否則必究法律責任

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/499767.html

標籤：其他

上一篇：背包問題

下一篇：2022杭電中超

素數演算法（Prime Num Algorithm）

素數演算法（Prime Num Algorithm）

1. 給定一個正整數\(n\), 判定該數是否為素數

1.1 初始演算法

1.1.1 演算法

1.1.2 代碼

1.1.3 演算法復雜度

1.2 演算法優化1

1.2.1 演算法

1.2.2 代碼

1.2.3 演算法復雜度

1.3 演算法優化2

1.3.1 證明

1.3.2 演算法

1.3.3 代碼

1.3.4 演算法復雜度

1.4 演算法優化結合

1.4.1 演算法

1.4.2 代碼

1.4.3 演算法復雜度

2. 給定一個正整數\(n\), 求取小于等于該數的所有素數列

2.1 初始演算法

2.1.1 演算法

2.1.2 代碼

2.1.3 演算法復雜度

2.2 演算法優化1

2.2.1 演算法

2.2.2 代碼

2.2.3 演算法復雜度

2.3 演算法優化2

2.3.1 演算法

2.3.2 代碼

2.3.3 演算法復雜度

2.4 演算法優化結合

2.4.1 演算法

2.4.2 代碼

2.4.3 演算法復雜度

3. 給定兩個正整數 \(n_1\), \(n_2\)(\(n_1 \le n_2\))， 求取 \(n_1\)到 \(n_2\)之間其所包含的素數列

3.1 演算法1

3.1.1 演算法

3.1.2 代碼

3.1.3 演算法復雜度

3.2 演算法2

3.2.1 演算法

3.2.2 代碼

3.2.3 演算法復雜度

4. 從\(2\)開始計算大素數

4.1 演算法1

4.1.1 演算法

4.1.2 代碼

4.1.3 演算法復雜度

3. 給定兩個正整數 \(n_1\), \(n_2\)(\(n_1 \le n_2\))，求取 \(n_1\)到 \(n_2\)之間其所包含的素數列