Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

LeetCode 204. Count Primes计数质数 (C++)

silentteller 2019-09-11 16:05:00 阅读数:10 评论数:0 点赞数:0 收藏数:0

题目:

Count the number of prime numbers less than a non-negative number, n.

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

分析:

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

这里使用埃拉托斯特尼筛法。要得到自然数n以内的全部素数,必须把不大于√n的所有素数的倍数剔除,剩下的就是素数。

例如我们要求2-25以内素数的个数,

2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25

第一次先剔除掉2以后的倍数

2,3,5,7,9,11,13,15,17,19,21,23,25

接下来剔除3的倍数

2,3,5,7,11,13,17,19,23,25

接下来剔除5的倍数

2,3,5,7,11,13,17,19,23

由于7 > √25,算法停止。

我们可以初始化大小为n的数组res,其内所有元素均为1,默认所有数字均为素数,首先将0,1剔除掉,然后开始执行算法,当前元素i,若res[i]==1,将i的倍数全部置为0,若res[i]==0,则继续执行,注意本题是求小于n的素数的个数,终止条件设为小于sqrt(n)即可,若包括n,则需要小于等于sqrt(n)。

程序:

class Solution {
public:
    int countPrimes(int n) {
        if(n < ) return ;
        vector<int> res(n, );
        res[] = ;
        res[] = ;
        for(int i = ; i < sqrt(n); ++i){
            if(res[i] != )
                continue;
            for(int j = i*; j < n; j += i){
                res[j] = ;
            }
        }
        int num = count(res.begin(), res.end(), );
        return num;
    }
};
版权声明
本文为[silentteller]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/silentteller/p/11506832.html