leetcode 204. 计数质数

2022-02-14

题目

给定整数 n ，返回所有小于非负整数 n 的质数的数量。

示例1:
n = 10
输出：4
解释：小于10的质数一共有4个。分别为2 3 5 7

数据量：0 <= n <= 5*10^6

难度：Medium

点这里做题

思路

暴力肯定超时，这里学习一下埃氏筛的做法

用一个isPrime数组标记i是否为质数，如果它是的话，就把2i 3i 4i .. 都标记为非质数

这里可以优化：对于一个质数x，应该从x*x开始标记它的倍数。2x 3x等这些数一定在x之前就被其他数的倍数标记

知识点：埃氏筛

代码

class Solution {
public:
    int countPrimes(int n) {
        vector<int> isPrime(n, 1);
        int ans = 0;
        for(int i=2;i<n;++i){
            if(isPrime[i]){
                ++ans;
                if((long long) i*i < n)
                    for(int j=i*i;j<n;j+=i){
                        isPrime[j] = 0;
                    }
            }
        }
        return ans;
    }
};