埃拉托斯特尼篩法，簡稱埃氏篩或愛氏篩，是一種由希臘數學家埃拉托斯特尼所提出的一種簡單檢定素數的算法。要得到自然數n以內的全部素數，必須把不大于根號n的所有素數的倍數剔除，剩下的就是素數。
給出要篩數值的范圍n，找出以內的素數。先用2去篩，即把2留下，把2的倍數剔除掉；再用下一個質數，也就是3篩，把3留下，把3的倍數剔除掉；接下去用下一個質數5篩，把5留下，把5的倍數剔除掉；不斷重復下去......。
java源碼：
~~~
package test1.number;
public class Eratosthenes {
public static void main(String[] args) {
int max = 20;
try {
max = Integer.parseInt(args[0]);
}
catch (Exception e) {
}
boolean[] isprime = new boolean[max + 1];
for (int i = 0; i <= max; i++)
isprime[i] = true;
isprime[0] = isprime[1] = false;
int n = (int) Math.ceil(Math.sqrt(max));
for (int i = 0; i <= n; i++) {
if (isprime[i])
for (int j = 2 * i; j <= max; j = j + i)
isprime[j] = false;
}
int largest;
for (largest = max; !isprime[largest]; largest--);
System.out.println("The largest prime less than or equal to " + max
+ " is " + largest);
}
}
~~~
運行結果：
