素数算法（Prime Num Algorithm）

素数算法（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 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$是否为素数，我们只需要判定

1. 该数是是否是$2$。
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{array}{}\text{(1)}& z_1\cdot z_2& \ge (\lfloor \sqrt{n}\rfloor +k_1)(\lfloor \sqrt{n}\rfloor +k_2)\text{(2)}& & \ge (\lfloor \sqrt{n}\rfloor +1)(\lfloor \sqrt{n}\rfloor +1)\text{(3)}& & =(\lfloor \sqrt{n}\rfloor +1{)}^2\text{(4)}& & >n\end{array}$$

为什么$(\lfloor \sqrt{n}\rfloor +1{)}^2>n$，因为$\lfloor \sqrt{n}\rfloor +1>\sqrt{n}$。这里将$\sqrt{n}$取值为任意一正实数$r$，我们可以得知任意正实数$r$的向下取整$\lfloor r\rfloor$满足：

$$\{\begin{array}{rlr}\lfloor r\rfloor & =r& ,ifr\in Z_{+}\\ \lfloor r\rfloor & >r-1& ,ifr\notin Z_{+}\end{array}$$

于是，

$$\{\begin{array}{rlr}\lfloor r\rfloor +1=r+1& >r& ,ifr\in Z_{+}\\ \lfloor r\rfloor +1>(r-1)+1& =r& ,ifr\notin Z_{+}\end{array}$$

证毕。

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$是否为素数，我们只需要判定

1. 该数是是否是$2$。
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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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)$

注： 虽然算法复杂度没有变，但是执行时间上，使用递归的方式还是比循环的方式慢了不少，我想可能跟递归成本高有很大关系。