埃拉托斯特尼筛法检定素数
最后更新于：2022-04-01 20:25:03
埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数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);
}
}
~~~
运行结果：
';