[数据结构与算法]数据结构与算法2（计数质数）

1 问题

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

1.1 示例

1.1.1 示例1：

????????输入：n = 10
????????输出：4

1.1.2 示例 2：

????????输入：n = 0
????????输出：0

1.1.3 示例 3：

????????输入：n = 1
????????输出：0

2 思路

2.1 遍历法

?图1 遍历

2.2 埃筛法

图2 埃筛法

?3 编程

3.1 遍历

class Solution {
public:
    int countPrimes(int n) {

        int count = 0;
        for(int i=2; i<n; i++)
        {
            count += isPrime(i);
        }
        return count;
    }

    bool isPrime(int x)
    {
        for(int i=2; i*i<=x; i++)
        {
            if(x % i == 0)
            {
                return false;
            }
        }
        return true;
    }
};

3.2 埃筛法

class Solution {
public:
    int countPrimes(int n) {

        int count = 0;
        vector<bool> signs(n, true); //true为素数

        for (int i=2; i<n; i++)
        {
            if (signs[i])
            {
                count++;
                for (int j=2*i; j<n; j+=i)
                {
                    signs[j] = false;
                }
            }
        }

        return count;
    }
};