複製代碼代碼如下:
/**
* @author jxqlovedn
* 埃拉托斯特尼素數篩選法，請參考：http://zh.wikipedia.org/zh-cn/埃拉托斯特尼篩法
*/
public class AratosternyAlgorithm {
public static void getPrimes(int n) {
if(n < 2 || n > 1000000) // 之所以限制最大值為100萬，是因為JVM記憶體限制，當然有其他彈性方案可以繞過（例如點陣圖法）
throw new IllegalArgumentException("輸入參數n錯誤！");
int[] array = new int[n]; // 假設初始所有數都是質數，且某個數是質數，則其值為0；例如第一個數為質數那麼array[0]為0
array[0] = 1; // 0不是質數
array[1] = 1; // 1不是質數
// 下面是篩選核心過程
for(int i = 2; i < Math.sqrt(n);i++) { // 從最小質數2開始
if(array[i] == 0) {
for(int j = i*i; j < n; j += i) {
array[j] = 1; // 標識該位置為非素數
}
}
}
// 列印n以內的所有質數，每排10個輸出
System.out.println(n + "以內的質數如下： ");
int count = 0; // 目前已經輸出的質數個數
int rowLength = 10; // 每行輸出的質數個數
for(int i = 0; i < array.length; i++) {
if(array[i] == 0) {
if(count % rowLength == 0 && count != 0) {
System.out.println();
}
count++;
System.out.print(i + "/t");
}
}
}
public static void main(String[] args) {
getPrimes(99999);
}
}