求质数的方法

看java核心，有一求质数的程序：

public class Sieve {
	public static void main(String[] s) {
		int n = 2000000;
		long start = System.currentTimeMillis();
		BitSet b = new BitSet(n + 1);//用于记录是否为质数
		int count = 0;
		int i;
		for (i = 2; i <= n; i++){
			b.set(i);             //初始化
		}
		//忽略 1
		i = 2;
		while (i * i <= n) {
			if (b.get(i)) {
				count++;
				//清除所有i的倍数
				int k = 2 * i;
				while (k <= n) {
					b.clear(k);
					k += i;
				}
			}
			i++;
		}
		//处理剩余没处理的
		while (i <= n) {
			if (b.get(i))
				count++;
			i++;
		}
		long end = System.currentTimeMillis();
		System.out.println(count + " primes");
		System.out.println((end - start) + " milliseconds");
	}
}

 C语言版：

 using namespace std;

 int main() {
	 const int N = 2000000;
	 clock_t cstart = clock();

	 bitset<N + 1> b;
	 int count = 0;
	 int i;
	 for (i = 2; i <= N; i++)
		 b.set(i);
	 i = 2;
	 while (i * i <= N){
		 if (b.test(i)){
			 count++;
			 int k = 2 * i;
			 while (k <= N) {
				 b.reset(k);
				 k += i;
			 }
		 }
		 i++;
	 }
	 while (i <= N) {
		 if (b.test(i))
			 count++;
		 i++;
	 }

	 clock_t cend = clock();
	 double millis = 1000.0 * (cend - cstart) / CLOCKS_PER_SEC;

	 cout << count << " primes\n"
	 	<< millis << " milliseconds\n";

	 return 0;
}