【LeetCode 204】关关的刷题日记39 Count Primes- 专知

会员服务 ·

【LeetCode 204】关关的刷题日记39 Count Primes

关关

点击上方“专知”，关注获取专业AI知识”

关关的刷题日记39–Leetcode 204. Count Primes

题目

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

题目的意思是让求小于n的素数的个数。

方法1：本来最简单的想法是遍历3到的数，都不是n的约数的就是素数，反之就是合数，结果超时了。后来师父给指点了下：如果一个数是合数的话，那么肯定有质因子，所以实际上我们只需要遍历3到之间的素数就可以了。

class Solution {public:    int countPrimes(int n) {        if(n<3)            return 0;        int re=0;        vector<int>primes;        primes.push_back(2);        for(int i=3; i<n; i=i+2)        {            int flag=1;            for(int x:primes)            {                if(x*x>n)                    break;                if(i%x==0)                {                    flag=0;                    break;                }            }            if(flag)                primes.push_back(i);        }        return primes.size();    }};

方法二：厄拉多塞筛法求素数。看了一下网上这一篇博客介绍得很好：http://blog.csdn.net/tsbyj/article/details/47254069，大家可以参考下。

class Solution {public:    int countPrimes(int n) {        if(n<3)            return 0;        int re=0;        vector<int>primes(n,1);        for(int i=2; i*i<n; ++i)        {            if(primes[i]==1)            {                for(int j=i; j*i<n; ++j)                {                    primes[i*j]=0;                }            }        }        for(int x:primes)        {            re+=x;        }        return re-2;    }};