Leetcode 204 Count Primes

triplebee

发布于 2018-01-12 14:47:16

3850

发布于 2018-01-12 14:47:16

文章被收录于专栏：计算机视觉与深度学习基础

Description:

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

统计小于n的素数有多少个。

用筛法进行素数打表，边打表边记录个数。

class Solution {
public:
    int countPrimes(int n) {
        vector<bool> mp(n, 0);
        int res = 0;
        for(int i = 2 ; i < n ; i++)
        {
            if(!mp[i])
            {
                res++;
                if(i <= sqrt(n)) for(int j = i * i ; j < n ;j += i) mp[j] = 1;
            }
        }
        return res;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017-03-16 ，如有侵权请联系 cloudcommunity@tencent.com 删除

numbers