用篩選法求解n以內的所有素數：篩選法的思想是一個數是素數則這個數的所有的倍數都是合數，我們不去找素數而去找合數，剩下的就是素數了。一個合數其最大的質因子不會超過其開發數,所以只要迭代到其最大數的開方數即可 一個簡單的篩素數的過程：n=30。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

第 1 步過后2 4 ... 28 30這15個單元被標成false,其余為true。

第 2 步開始：

i=3; 由于prime[3]=true, 把prime[6], [9], [12], [15], [18], [21], [24], [27], [30]標為false.

i=4; 由于prime[4]=false,不在繼續篩法步驟。

i=5; 由于prime[5]=true, 把prime[10],[15],[20],[25],[30]標為false.

i=6>sqrt(30)算法結束。

第 3 步把prime[]值為true的下標輸出來：

控制臺輸出

用篩選法求解30以內的所有素數：

2 3 5 7 11 13 17 19 23 29

Process finished with exit code 0

代碼如下

package AlgorithmTest;

/**

* Created by dell on 2016/12/18.

*/

//一個簡單的篩素數的過程：n=30。

// 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

//

// 第 1 步過后2 4 ... 28 30這15個單元被標成false,其余為true。

// 第 2 步開始：

// i=3; 由于prime[3]=true, 把prime[6], [9], [12], [15], [18], [21], [24], [27], [30]標為false.

// i=4; 由于prime[4]=false,不在繼續篩法步驟。

// i=5; 由于prime[5]=true, 把prime[10],[15],[20],[25],[30]標為false.

// i=6>sqrt(30)算法結束。

// 第 3 步把prime[]值為true的下標輸出來：

public class Sushu {

public static void main(String[] args) {

System.out.println("用篩選法求解30以內的所有素數：");

printSushu(30);

}

public static void printSushu(int n){

if ( n <= 1){

System.out.println("輸入錯誤");

}

boolean[] isPrimes = new boolean[n + 1];

for (int i = 0 ; i < isPrimes.length; i++){

isPrimes[i] = true;

}

for (int j = 4; j <= n; j += 2){

isPrimes[j] = false;

}

for (int j = 3; j < Math.sqrt(n); j++){

if (isPrimes[j]){//如果是素數則其所有的倍數都是合數

for (int i = j + j ; i <= n; i = i + j){

isPrimes[i] = false;

}

}

}

for (int i = 2; i < isPrimes.length; i++){

if (isPrimes[i]){

System.out.print(i + " ");

}

}

}

}

總結

以上是生活随笔為你收集整理的python用筛选法求解小于n的所有素数_用筛选法求解n以内的所有素数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。