昨天自己看《Java核心技术》的时候看到了这种实现查找素数的算法,决定把它记录下来。
Eratosthenes筛子算法的思想是如果一个数是素数的倍数,则这个数不是素数。
实现源码如下:
import java.util.*;
public class Sieve{
public static void main(String[] args){
int n = 5;
BitSet b = new BitSet(n + 1);
int count = 0;
int i;
for(i = 2;i <= n;i ++){
b.set(i);
}
i = 2;
while(i * i <= n){
if(b.get(i)){
count ++;
int k = 2 * i;
while(k <= n){
b.clear(k);
k += i;
}
}
i ++;
}
while(i <= n){
if(b.get(i))
count ++;
i ++;
}
System.out.println("count " + count);
}
}
网友评论