求某个数内所有的质数

最近发现有一个类：java.util.BitSet，挺好用的。

 

例如在求某个数下所有的质数，可以如下实现：

	public static int[] listPrimesUnder(int number) {
		assert number > 1;
		int count = 0;
		BitSet bs = new BitSet(number);
		for (int i = 2; i <= number; i++) {
			if (bs.get(i - 1)) {
				continue;
			}
			count++;
			int t = i + i;
			while (t <= number) {
				bs.set(t - 1);
				t += i;
			}
		}
		int[] results = new int[count];
		count = 0;
		for (int i = 2; i <= number; i++) {
			if (!bs.get(i - 1)) {
				results[count++] = i;
			}
		}
		return results;
	}

 首先用bitset对象作个占位符，把非质数的数先标识出来。最后再一遍，把质数的数填充返回内容。

 

例如100以内的质数有：

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97