🌕🌗 204. 计数质数

难度: 🌕🌗

问题描述

---

解法

class Solution {
    public int countPrimes(int n) {
        // 思路：
        // 从第一个已知质数开始，标记它的倍数，那么这些数就不可能是质数
        // 依次往下查找下一个质数，例 3，也开始标记它的倍数，如此循环
        // 最后统计没有被标记是数的个数，这些数就是质数
        if(n < 2) {
            return 0;
        }
        // n >= 2
        int[] array = new int[n];
        // 从 2 开始判断，计数时也从2 开始计数
        for(int i = 2; i < n; i ++) {
            if(array[i] == 0) {
                // 说明是质数，标记它的倍数
                for(int j = i; j <= n / i; j ++) {
                    if(j * i < n &&  array[j * i] == 0) {
                        array[j * i] = 1;
                    }
                }
            }
        }
        // 计数
        int res = 0;
        for(int i = 2; i < n; i ++) {
            if(array[i] == 0) {
                res ++;
            }
        }
        return res;
    }
}

---

输出