计算N以内的质数

日常无聊编码之高效率地计算N以内的质数。

备注：最开始使用的Java的BitSet实现的，后来发现用boolean数组效率更高。

代码如下:

public static boolean[] getPrimes(int n) {
    boolean[] primes = new boolean[n + 1];
    primes[2] = true;
    for (int i = 3; i <= n; i += 2) {
        primes[i] = true;
    }
    int factor = (int) Math.sqrt(n);
    for (int i = 3; i <= factor; i += 2) {
        if (primes[i]) {
            int j = i * i;
            int m = i;
            while (j <= n) {
                primes[j] = false;
                while (n / j >= i) {
                    j *= i;
                    primes[j] = false;
                }
                m += 2;
                while (!primes[m]) {
                    m += 2;
                }
                j = i * m;
            }
        }
    }
    return primes;
}

计算100000000以内的所有质数耗时638毫秒，结果如下：