Leetcode#204-计数质数

题目描述

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

示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2：
输入：n = 0
输出：0

示例 3：
输入：n = 1
输出：0

提示：
0 <= n <= 5 * 106

解题思路

枚举-略
埃式筛-如果 x 是质数，那么大于 x 的倍数 2x,3x,… 一定不是质数，设 isPrime[i] 表示数 i是不是质数，如果是质数则为 1，否则为 0。从小到大遍历每个数，如果这个数为质数，则将其所有的倍数都标记为合数（除了该质数本身），即 0，这样在运行结束的时候我们即能知道质数的个数。继续优化，对于一个质数 x，如果按上文说的我们从 2x 开始标记其实是冗余的，应该直接从 x⋅x 开始标记，因为 2x,3x,… 这些数一定在 x 之前就被其他数的倍数标记过了，例如 2 的所有倍数，3 的所有倍数等。时间复杂度O(nloglogn)。

leetcode官方题解

源码

class Solution {
public:
    bool isPrime(int n)
    {
        if(n<2)return false;
        if(n==2||n==3||n==5||n==7)return true;
        for(int i=2;i*i<=n;i++)
        {
            if(n%i==0)return false;
        }
        return true;
    }
    int countPrimes(int n) {
        /*
        int ans=0;
        for(int i=0;i<n;i++)
        {
            if(isPrime(i))ans++;
        }
        return ans;
        */
        
        //埃式筛-get 新知识
        vector<int> isPri(n,1);
        int ans=0;
        for(int i=2;i<n;i++)
        {
            if(isPri[i])
            {
                ans++;
                if((long long)i*i<n)
                {
                    for(int j=i*i;j<n;j+=i)
                    {
                        isPri[j]=0;
                    }
                }
            }
        }
        return ans;
    }
};

题目来源

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。