素数算法（Prime Num Algorithm） - 论语
source link: https://www.cnblogs.com/lunyu/p/16495874.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
素数算法（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, 求取小于等于该数的所有素数列。
- 给定两个正整数 n1, n2(n1≤n2)， 求取 n1到 n2之间其所包含的素数列。
- 从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(n2) | O(1) |
1.3 算法优化2
实际上，判定一个整数n是否为素数，我们可以缩减判定的范围，将之前的全量比较，变更为，判定该整数是否不能被其开方后的整数向下取整（⌊n⌋）以内（含⌊n⌋）的非1整数所整除。
直观一点，即自然数n，能否不被整数列集合{x|2≤x≤⌊n⌋,x∈Z+}所整除。
这个优化判定是可以证明的。我们来给出证明。
1.3.1 证明
设有正整数n,它不能被其开方后的整数向下取整（⌊n⌋）以内（含⌊n⌋）的非1整数所整除，我们证明它一定是一个素数。
我们用反证法。
假设它是一个合数，那么它一定可以表示成两个非1整数z1⋅z2乘积的形式。
我们又已知，它不能被其开方后的整数向下取整（⌊n⌋）以内（含⌊n⌋）的非1整数所整除，因此无论是z1还是z2，都不可能包含1到⌊n⌋之间的素因子，否则与n不能被1到（⌊n⌋）的非1整数所整除矛盾。
于是，无论是z1还是z2都必包含大于⌊n⌋的素因子，这两个素因子分别记作⌊n⌋+k1,⌊n⌋+k2（k1,k2≥1）。
为什么(⌊n⌋+1)2>n，因为⌊n⌋+1>n。这里将n取值为任意一正实数r，我们可以得知任意正实数r的向下取整⌊r⌋满足：
1.3.2 算法
判定一个整数n是否为素数，只需判定该整数是否不能被其开方后的整数向下取整（⌊n⌋）以内（含⌊n⌋）的非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(n12) | O(1) |
1.4 算法优化结合
我们可以将1.2 算法优化1和1.3 算法优化2结合起来，形成一个更优算法。
1.4.1 算法
判定一个整数n是否为素数，我们只需要判定
- 该数是是否是2。
- 在该数不为2的情形下，该数是否不被以下数所整除：
- 不被2整除，
- 不被其开方后的整数向下取整（⌊n⌋）以内（含⌊n⌋）的非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(12n12) | 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⋅n)也即O(n2)。
而空间复杂度，因为我们有素数列的采集动作，因此这里空间复杂度不是O(1)，而是O(n/lnn)。这里的值取自素数定理，即一个自然数x以内的素数个数π(x)，其渐进估计为π(x)∼x/lnx。
| 时间复杂度 | 空间复杂度 |
|---|---|
| O(n2) | O(n/lnn) |
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(12n),内层时间复杂度为O(12n12)，因此总的时间复杂度为O(14n32)。
空间复杂度不变，仍为O(n/lnn)。
| 时间复杂度 | 空间复杂度 |
|---|---|
| O(14n32) | O(n/lnn) |
2.3 算法优化2
1.3 算法优化2中，判定一个整数是否为素数，即判定该数是否不能被其开方后的整数向下取整（⌊n⌋）以内（含⌊n⌋）的非1整数所整除。
这个地方的判定，我们可以进一步优化为，判定一个整数是否为素数，即判定该数是否不能被其开方后的整数向下取整（⌊n⌋）以内（含⌊n⌋）的非1素数所整除。
直观一点，即自然数n，能否不被素数列集合{x|2≤x≤⌊n⌋,x∈P+}所整除。
证明略，同1.3.1 算法优化2-证明。
有了以上优化点，我们还缺少素数列集合{x|2≤x≤⌊n⌋,x∈P+}，幸运的是，我们的目标“给定一个正整数n, 求取小于等于该数的所有素数列”即隐含的包含该信息，也即殊途同归，目标基本一致。有了这些条件，我们就可以对2.1 初始算法进行一定的优化。
2.3.1 算法
给定一个正整数n, 求取小于等于该数的所有素数列, 即
对从2到n的每一个整数，我们依次判定该数是否为素数。如果为素数，我们将该数存储起来得到的素数列。
判定是否为素数的法则为，该数能否不被素数列集合{x|2≤x≤⌊n⌋,x∈P+}所整除。
素数列集合{x|2≤x≤⌊n⌋,x∈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≤x≤⌊n⌋,x∈P+}的时间复杂度为O(n12/lnn12)=O(12n12/lnn),因此总的时间复杂度为O(12n32/lnn)。
获得素数列，其空间复杂度为O(n/lnn)。
| 时间复杂度 | 空间复杂度 |
|---|---|
| O(12n32/lnn) | O(n/lnn) |
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(n2)；内层, 遍历素数列集合{x|2≤x≤⌊n⌋,x∈P+}的时间复杂度为O(n12/lnn12)=O(12n12/lnn),因此总的时间复杂度为O(14n32/lnn)。
获得素数列，其空间复杂度为O(n/lnn)。
| 时间复杂度 | 空间复杂度 |
|---|---|
| O(14n32/lnn) | O(n/lnn) |
3. 给定两个正整数 n1, n2(n1≤n2)， 求取 n1到 n2之间其所包含的素数列
这里有两种方式可以解决问题：
第一种对n1到 n2之间整数，我们依次判定是否为素数，如果为素数，我们将它们采集起来得到素数列即为所求。
第二种，我们先求出小于等于n2的所有素数列，再将该素数列中介于n1, n2的素数列（{x|n1≤x≤n2,x∈P+}）取出即为所求。
3.1 算法1
为了减少篇幅，这里直接使用1.4 算法优化结合中的算法，而不从头开始逐步优化。
3.1.1 算法
给定两个正整数 n1, n2(n1≤n2)， 求取 n1到 n2之间其所包含的素数列，即
对n1到 n2之间整数，我们依次判定是否为素数，如果为素数，我们将它们采集起来得到素数列即为所求。
判定素数算法为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(n2−n1)，内层循环时间复杂度是O(12n212)，于是总的时间复杂度为O(12n212(n2−n1))。
因为有素数列的采集动作，因此这里空间复杂度是O(n2/lnn2−n1/lnn1)。
| 时间复杂度 | 空间复杂度 |
|---|---|
| O(12n212(n2−n1)) | O(n2/lnn2−n1/lnn1) |
注： 上述算法还能再进一步优化，在外层循环中，我们处理好n1，n2可能存在的=2这个特殊情况后，其中的循环变量，只取介于n1到n2的奇数进行判定，这样时间复杂度可减半，变为O(14n212(n2−n1))。
3.2 算法2
同样为了减少篇幅，我们直接使用2.4 算法优化结合中的算法，而不从头开始逐步优化。
3.2.1 算法
给定两个正整数 n1, n2(n1≤n2)， 求取 n1到 n2之间其所包含的素数列，即
先求出小于等于n2的所有素数列，再将介于n1到 n2之间素数取出即为所求。
求出小于等于n2的所有素数列算法取自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(n22)；内层, 遍历素数列集合{x|2≤x≤⌊n⌋,x∈P+}的时间复杂度为O(n212/lnn212)=O(12n212/lnn2),因此总的时间复杂度为O(14n232/lnn2)。
获得素数列，其空间复杂度为O(n2/lnn2)，获得介于 n1, n2的素数列，其空间复杂度为O(n2/lnn2−n1/lnn1)，于是总的空间复杂度为O(2n2/lnn2−n1/lnn1)。
| 时间复杂度 | 空间复杂度 |
|---|---|
| O(14n232/lnn2) | O(2n2/lnn2−n1/lnn1) |
4. 从2开始计算大素数
从计算机诞生以来，计算超大素数就成为了可能。目前最大的已知素数为(282,589,933−1)（来自网络），足有2500万位。计算大素数、超大素数可以用来验证很多有关素数的问题。
本文即从算法可行的角度，从2开始来计算大素数，并对计算过程进行一定的优化。
4.1 算法1
我们怎么计算大素数呢？这里我要反其道而行之。先算一部分，然后再算一部分，最后算到我们想要的数为止。说的太含混了，下面以例子进行说明。
首先，我们先获取到素数2，构成初始素数列{2}。我们取其中最大的素数，即2。我们知道22=4，于是，我们可以得到大于2且小于22的奇数列{3} 。我们判定这个数列中不能被初始素数列{2}整除的数，得到数列{3} 。我们将初始素数列{2}和新得到的数列{3}合并得到小于4的素数列{2,3}。
进行第二次循环。我们已知初始素数列{2,3}。取其中最大的素数，即3。我们知道32=9，于是，我们可以得到大于3且小于32的奇数列{5,7} 。我们判定这个数列中不能被已知初始素数列{2,3}所整除的数，得到数列{5,7}。我们将初始素数列{2,3}和新得到的数列{5,7}合并得到小于9的素数列{2,3,5,7}。
进行第三次循环。我们已知初始素数列{2,3,5,7}。取其中最大的素数，即7。我们知道72=49，于是，我们可以得到大于7且小于72的奇数列{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,…,pk},k≥2。我们取其中最大的奇素数，即pk。我们可以得到大于pk且小于pk2的奇数列{pk+2,…,pk2−2} 。我们判定这个数列中不能被初始素数列{2,…,pk},k≥2整除的数，得到数列{pk+1,…,pl} 。我们将初始素数列{2,3,…,pk},k≥2和新得到的素数列{pk+1,…,pl}合并得到小于pk2的素数列{2,3,…,pl},l≥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(14n32/lnn) | O(n/lnn) |
注： 虽然算法复杂度没有变，但是执行时间上，使用递归的方式还是比循环的方式慢了不少，我想可能跟递归成本高有很大关系。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK