從2開始，刪除所有2的倍數的數。
然后是3，5，7，...
下一次循環進行時的第一個數一定是素數。
只進行sqrt(n)次循環，因為一個數的約數只在sqrt(n)這個范圍內。
import java.util.BitSet;
import java.util.LinkedList;
import java.util.List;
public class Test {
public static void main(String[] args) {
int n = 100;
BitSet b = new BitSet(n + 1);
List<Integer> primes = new LinkedList<Integer>();
int i = 0;
for (i = 2; i <= n; ++i) {
b.set(i); // 設置此位置上的位為1
}
i = 2;
int k = 0;
while (i * i <= n) {
if (b.get(i)) {
primes.add(i);
k = 2 * i;
while (k <= n) {
b.clear(k); // 清除此位置上的位為0
k += i;
}
}
++i;
}
while (i <= n) {
if (b.get(i)) {
primes.add(i);
}
++i;
}
System.out.println(primes);
}
}