10 万以内素数的个数（几种计算方式）

素数的定义是：只能被 1 和它本身整除，其中 1 不是素数，2 是最小的素数。

如何计算 10 万以内的素数呢？

暴力破解法

首先可以想到，使用暴力的方法，对于 2 ~ 100000 之间的数字 k，都一个一个试着除以 [2, k-1] 内的数字 i

• 如果存在余数为 0 的情况（ k % i == 0）则说明可以被除尽。

    public int method01(int n) {
        int count = n - 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j < i; j++) {
                if (i % j == 0) {
                    count--;
                    break;
                }
            }
        }
        return count;
    }

暴力法的优化

优化 1：一个数字的最小因数是 2，而与之相对的 n/2 可以充当上边界，超过这个范围就重复了

优化 2：一般来说，一个数字的一对公因数中都是一大一小，例如 64 的最左边的一对公因数是 2 x 32 他们两个分别是最小和最大的公因数。这个 32 也是之前说的上边界，但是这个上边界还可以更小！
一对相差最小的公因数是 8 x 8. 刚好是该数字的平方根。

    // 取中间数
    public int method02(int n) {
        int count = n - 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= i / 2; j++) {
                if (i % j == 0) {
                    count--;
                    break;
                }
            }
        }
        return count;
    }

    // 取平方根
    public int method03(int n) {
        int count = n - 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    count--;
                    break;
                }
            }
        }
        return count;
    }

埃式筛法

    // 埃氏筛法
    public int method04(int n) {
        int num[] = new int[n];
        num[0] = 1;
        double prescription = Math.sqrt(n);
        for (int i = 2; i <= prescription; i++) {
            if (num[i-1] == 0) {
                for (int j = i * i; j <= n; j += i) {
                    num[j - 1] = 1;
                }
            }
        }
        int count = 0;
        // 遍历数组，把值为0的数全部统计出来，得到素数的个数
        for (int i = 0; i < n; i++) {
            if (num[i] == 0)
                count++;
        }
        return count;
    }

输出结果

计算 10万 以内的素数个数

暴力法：9592个素数
耗时：1.501 秒
-------------------------------------------------------
优化——取中间数：9592个素数
耗时：1.045 秒
-------------------------------------------------------
优化——取平方根：9592个素数
耗时：0.023 秒
-------------------------------------------------------
埃氏筛法：9592个素数
耗时：0.002 秒
-------------------------------------------------------
未知算法（挺快的）：9592个素数
耗时：0.002 秒
-------------------------------------------------------