Leetcode 204 Count Primes

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;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 264. Ugly Number II

    Write a program to find the n-th ugly number. Ugly numbers are positive number...

    triplebee
  • Leetcode 29 Divide Two Integers 位操作的巧妙运用

    Divide two integers without using multiplication, division and mod operator. I...

    triplebee
  • Leetcode 52 N-Queens II

    Follow up for N-Queens problem. Now, instead outputting board configurations, ...

    triplebee
  • 一文为你揭秘深圳机场智慧航旅服务中的黑科技

    为了提升深圳机场的整体服务效率,腾讯云为深圳机场构建了一套【OneID全流程旅客出行服务系统】。顾名思义,OneID,也就是一个旅客ID,贯穿旅客在机场的出港、...

    腾讯云开发TCB
  • Android粒子篇之Bitmap像素级操作

    张风捷特烈
  • AnimatedPathView实现自定义图片标签

    老早用过小红书app,对于他们客户端笔记这块的设计非常喜欢,恰好去年在小红书的竞争对手公司,公司基于产品的考虑和产品的发展,也需要将app社交化,于是在社区分享...

    xiangzhihong
  • 这效果碉堡了!Bitmap粒子“爆炸”效果

    内容来源:作者 | 张风捷特烈,链接 | https://www.jianshu.com/p/12184d861646

    IT大咖说
  • Golang笔记 4.2 go 接口

    接口定义了一组方法(方法集),但是这些方法不包含(实现)代码:它们没有被实现(它们是抽象的)。

    twowinter
  • Leetcode Golang 77. Combinations.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/88916151

    anakinsun
  • [随缘一题]回溯法解决n皇后问题

    采用回溯法,即逐一位置放置,然后放置下一行,如果下一行没有合法位置,则回溯到上一行,调整位置,直到得到所有值.

    呼延十

扫码关注云+社区

领取腾讯云代金券