【LeetCode】204. 计数质数

题目链接：https://leetcode-cn.com/problems/count-primes/description/

题目描述

统计所有小于非负整数 n 的质数的数量。

示例

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

解决方法

解题思路：筛法求素数

class Solution {
public:
    int countPrimes(int n) {
        //筛法求素数
        vector<int> prime(n,1);
        for (int i=2;i<n;i++)
            for (int j=2*i;j<n;j+=i)
                prime[j]=0;
        
        int res=0;
        for (int i=2;i<n;i++)
            if (prime[i])
                res++;
        return res;
    }
};