數學是科學的皇后，而素數可以說是數學最為核心的概念之一。圍繞素數產生了很多偉大的故事，最為著名莫過於哥德巴赫猜想、素數定理和黎曼猜想（有趣的是，自牛頓以來的三個最偉大數學家，尤拉、高斯和黎曼，分別跟這些問題有著深刻的淵源）。我寫這篇文章不是要探討和解決這些偉大猜想和定理，而是迴歸問題本身，用計算機判定一個素數，以及求取特定正整數值下所包含的所有素數。這篇文章，算是自己對素數問題思考的一次總結。
先說一下素數的定義：
素數也叫質數，是隻能被 \(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
有了素數的定義，我們通過計算機程式來解決以下問題。
解決上述問題的核心演演算法都是埃拉託斯特尼篩法,簡稱埃氏篩選法。這個方法的內容即每當我們得到一個素數後，我們即將這個素數的所有倍數（\(2\)倍以上）的整數刪除，重複執行該過程，最後餘下來的一定是素數。
判定一個整數\(n\)是否為素數，我們只需要判定該整數是否不能被小於它的非\(1\)整數所整除。
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;
}
}
| 時間複雜度 | 空間複雜度 |
|---|---|
| \(O(n)\) | \(O(1)\) |
因為\(2\)是唯一的一個偶素數，因此，我們可以在判定時將\(2\)的情況特殊處理，並且每次只需判定小於該數的奇數的情況。
判定一個整數\(n\)是否為素數，我們只需要判定
/**
* 經過優化的給定一個正整數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;
}
| 時間複雜度 | 空間複雜度 |
|---|---|
| \(O(\frac{n}{2})\) | \(O(1)\) |
實際上，判定一個整數\(n\)是否為素數，我們可以縮減判定的範圍，將之前的全量比較，變更為，判定該整數是否不能被其開方後的整數向下取整（\(\lfloor \sqrt{n} \rfloor\)）以內（含\(\lfloor \sqrt{n} \rfloor\)）的非\(1\)整數所整除。
直觀一點，即自然數\(n\)，能否不被整數列集合\(\{x| 2\le x\le \lfloor \sqrt{n} \rfloor, x\in Z_+\}\)所整除。
這個優化判定是可以證明的。我們來給出證明。
設有正整數\(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\)）。
於是,
為什麼\((\lfloor \sqrt{n} \rfloor + 1)^2 \gt n\)，因為\(\lfloor \sqrt{n} \rfloor + 1 > \sqrt{n}\)。這裡將\(\sqrt{n}\)取值為任意一正實數\(r\)，我們可以得知任意正實數\(r\)的向下取整\(\lfloor r \rfloor\)滿足：
於是，
證畢。
判定一個整數\(n\)是否為素數，只需判定該整數是否不能被其開方後的整數向下取整（\(\lfloor \sqrt{n} \rfloor\)）以內（含\(\lfloor \sqrt{n} \rfloor\)）的非\(1\)整數所整除。
/**
* 經過優化的給定一個正整數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;
}
| 時間複雜度 | 空間複雜度 |
|---|---|
| \(O(n^{\frac{1}{2}})\) | \(O(1)\) |
我們可以將1.2 演演算法優化1和1.3 演演算法優化2結合起來，形成一個更優演演算法。
判定一個整數\(n\)是否為素數，我們只需要判定
/**
* 給定一個正整數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;
}
| 時間複雜度 | 空間複雜度 |
|---|---|
| \(O(\frac{1}{2} n^{\frac{1}{2}})\) | \(O(1)\) |
易知，該問題即是上一問題的序列化，也即將上一問題在外層再套一層for迴圈，平鋪展開後的問題。
於是，我們先給出一個初始演演算法。
給定一個正整數\(n\), 求取小於等於該數的所有素數列, 即
對從\(2\)到\(n\)的每一個整數，我們依次判定該數是否為素數。如果為素數，我們將該數儲存起來得到的素數列。
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;
}
}
因為多了外層的一層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.4 演演算法優化結合給出最終優化方案。
第二部分，我們對for迴圈內的資料進行一次簡單優化。同樣易知，\(n\)以內的素數除\(2\)意外都是奇素數，因此這裡我們可以將外層for迴圈判定的資料也減半。
給定一個正整數\(n\), 求取小於等於該數的所有素數列, 即
對\(2\)和從\(3\)到\(n\)的每一個奇數，我們依次判定該數是否為素數 (判定該數是否為素數，取自1.4.1 演演算法優化結合-演演算法)。
如果為素數，我們將該數儲存起來得到的素數列。
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;
}
易知外層的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})\) |
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 初始演演算法進行一定的優化。
給定一個正整數\(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_+\}\)，在計算過程中得到。
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;
}
易知，外層的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.2 演演算法優化1和2.3 演演算法優化2結合起來，形成一個更優演演算法。
給定一個正整數\(n\), 求取小於等於該數的所有素數列, 即
對\(2\)和從\(3\)到\(n\)的每一個奇數，我們依次判定該數是否為素數 (判定該數是否為素數，取自2.3.1 演演算法優化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;
}
}
易知，外層的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})\) |
這裡有兩種方式可以解決問題：
第一種對\(n_1\)到 \(n_2\)之間整數，我們依次判定是否為素數，如果為素數，我們將它們採集起來得到素數列即為所求。
第二種，我們先求出小於等於\(n_2\)的所有素數列，再將該素數列中介於\(n_1\), \(n_2\)的素數列（\(\{x | n_1 \le x \le n_2, x \in P_+ \}\)）取出即為所求。
為了減少篇幅，這裡直接使用1.4 演演算法優化結合中的演演算法，而不從頭開始逐步優化。
給定兩個正整數 \(n_1\), \(n_2\)(\(n_1 \le n_2\))， 求取 \(n_1\)到 \(n_2\)之間其所包含的素數列，即
對\(n_1\)到 \(n_2\)之間整數，我們依次判定是否為素數，如果為素數，我們將它們採集起來得到素數列即為所求。
判定素數演演算法為1.4.1 演演算法。
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;
}
}
易知外層迴圈時間複雜度為\(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))\)。
同樣為了減少篇幅，我們直接使用2.4 演演算法優化結合中的演演算法，而不從頭開始逐步優化。
給定兩個正整數 \(n_1\), \(n_2\)(\(n_1 \le n_2\))， 求取 \(n_1\)到 \(n_2\)之間其所包含的素數列，即
先求出小於等於\(n_2\)的所有素數列，再將介於\(n_1\)到 \(n_2\)之間素數取出即為所求。
求出小於等於\(n_2\)的所有素數列演演算法取自2.4.1 演演算法
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;
}
}
易知，外層的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})\) |
從計算機誕生以來，計算超大素數就成為了可能。目前最大的已知素數為\((2^{82,589,933}-1)\)（來自網路），足有\(2500\)萬位。計算大素數、超大素數可以用來驗證很多有關素數的問題。
本文即從演演算法可行的角度，從\(2\)開始來計算大素數，並對計算過程進行一定的優化。
我們怎麼計算大素數呢？這裡我要反其道而行之。先算一部分，然後再算一部分，最後算到我們想要的數為止。說的太含混了，下面以例子進行說明。
首先，我們先獲取到素數\(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\}\)。
以此類推。
我們可以用這種方式，一直計算下去，得到任意的大的素數（如果算力允許的話）。
從\(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\)。
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;
}
}
| 時間複雜度 | 空間複雜度 |
|---|---|
| \(O(\frac{1}{4}n^{\frac{3}{2}}/\ln n)\) | \(O(n/{\ln n})\) |
注： 雖然演演算法複雜度沒有變，但是執行時間上，使用遞迴的方式還是比迴圈的方式慢了不少，我想可能跟遞迴成本高有很大關係。