素数算法（Prime Num Algorithm）

技术分享 2年前 (2022-07-20) 0 999+

素数算法（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| 2le xle lfloor sqrt{n} rfloor, xin 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| 2le xle lfloor sqrt{n} rfloor, xin P_+})所整除。

证明略，同1.3.1 算法优化2-证明。

有了以上优化点，我们还缺少素数列集合({x| 2le xle lfloor sqrt{n} rfloor, xin P_+})，幸运的是，我们的目标“给定一个正整数(n), 求取小于等于该数的所有素数列”即隐含的包含该信息，也即殊途同归，目标基本一致。有了这些条件，我们就可以对2.1 初始算法进行一定的优化。

2.3.1 算法

给定一个正整数(n), 求取小于等于该数的所有素数列, 即

对从(2)到(n)的每一个整数，我们依次判定该数是否为素数。如果为素数，我们将该数存储起来得到的素数列。

判定是否为素数的法则为，该数能否不被素数列集合({x| 2le xle lfloor sqrt{n} rfloor, xin P_+})所整除。

素数列集合({x| 2le xle lfloor sqrt{n} rfloor, xin 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| 2le xle lfloor sqrt{n} rfloor, xin 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| 2le xle lfloor sqrt{n} rfloor, xin 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| 2le xle lfloor sqrt{n} rfloor, xin 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;     }  }