关关的刷题日记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;
    }
};

人生易老，唯有陪伴最长情，加油！

以上就是关关关于这道题的总结经验，希望大家能够理解，有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390，也可以加入专知——Leetcode刷题交流群（请先加微信小助手weixinhao: Rancho_Fang）。 同时请，关注我们的公众号，获取最新关于专知以及人工智能的资讯、技术、算法等内容。扫一扫下方关注我们的微信公众号。