素数算法（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})/) |
注： 虽然算法复杂度没有变，但是执行时间上，使用递归的方式还是比循环的方式慢了不少，我想可能跟递归成本高有很大关系。
原创文章，作者：Carrie001128，如若转载，请注明出处：https://blog.ytso.com/275483.html