leetcode-204.计数质数

数学问题

---

题目详情

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

---

示例1：

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

示例2:

输入：n = 0
输出：0

示例3:

输入：n = 1
输出：0

思路:
本题利用埃拉托斯特尼筛法,简称埃氏筛法,它可以判断一个数是否是质数,并且它可以在判断一个整数 n 时，同时判断所小于 n 的整数
原理:
从 1 到 n 遍历，假设当前遍历到 m，则把所有小于 n 的、且是 m 的倍
数的整数标为和数；遍历完成后，没有被标为和数的数字即为质数。

我的代码：

class Solution 
{
    
public:
    int countPrimes(int n) 
    {
    
        if (n <= 2) return 0; //特殊情况
        vector<bool> prime(n, true); //标记数组prime初始化为true
        int count = n - 2;  //初始化-不包括n所以减1,1不是质数所以再减1
        for (int i = 2; i < n; ++i) //遍历
        {
    
            if (prime[i])  //如果i没有被标为和数(false)
            {
    
                //就从2i开始遍历i的倍数(保证小于n)
                for (int j = 2 * i; j < n; j += i)
                {
    
                    //如果遍历的倍数没有被标记过
                    if (prime[j])
                    {
    
                        prime[j] = false;   //标记
                        --count;            //标记一个 质数就减少一个
                    }
                }
            }
        }
        return count;  //返回数量
    }
};

这里可以利用质数的性质,来优化代码避免重复的冗余判断:

class Solution 
{
    
public:
    int countPrimes(int n) 
    {
    
        if (n <= 2) return 0;
        vector<int> prime(n, true);
        //因为1不是 2是质数,其余更大的偶数都不是质数
        //所以这里i直接从3开始,count直接折半(除去偶数,2也除去了,但是1算上了,所以恰好是n/2个)
        int i = 3, sqrtn = sqrt(n), count = n / 2;      
	//n的最小质因子一定小于等于sqrt(n) 
	//如9的最小质因子3,6的最小质因子2,10的最小质因子2
        while (i <= sqrtn)
        {
    
            //从i*i开始从而避免重复遍历 每次+=2*i从而避免判断偶数
            for (int j = i * i; j < n; j += 2 * i) 
            {
    
                if (prime[j])  //这里还是这样,如果没被标记过就标记上,质数数量--
                {
    
                    prime[j] = false;
                    --count;
                }
            }
            do
            {
    
                i += 2;  //避免偶数
            }
            while (i <= sqrtn && !prime[i]); //如果i被标记过就直接跳过判断,避免重复判断
           
        }
        return count;
    }
};

为什么循环里的判断条件是那样的?
从i * i开始筛选为什么?不是应该从2 * i开始嘛?
这里的原因是:对于一个质数 x，如果按上文说的我们从 2x 开始标记其实是冗余的，应该直接从 x * x 开始标记，因为 2x,3x… 这些数一定在 x 之前就被其他数的倍数标记过了，如 2 的所有倍数，3 的所有倍数等。
另外通过循环内部的do while循环避免了偶数和标记过带来的重复判断