LeetCode 204. Count Primes[通俗易懂]

LeetCode 204. Count Primes

大家好,又见面了,我是全栈君。

LeetCode原题维基百科都有解释用到的Sieve of Eratosthenes算法。
该算法可在O(nloglogn)时间内,求出小于n的全部质数;空间复杂度为O(n).
随着n的增大。当空间有限时。维基百科还提出了一种分段筛选(segmented sieve)方法。在时间复杂度不变的情况下,将空间复杂度降为O(n^0.5).

以下代码实现了常规筛选(regular sieve)方法:

class Solution 
{
public:
    int countPrimes(int n) 
    {
        if (n <= 1)
        {
            return 0;
        }

        bool prime[n];
        memset(prime, true, sizeof(prime));
        for (int i = 2; i * i < n; ++ i)
        {
            if (prime[i] == false)
            {
                continue;
            }
            for (int j = i * i; j < n; j += i)
            {
                prime[j] = false;
            }
        }
        return count_if(prime+2, prime+n, [](bool prime) -> bool { return prime;});
    }
};

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115376.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • node环境变量配置,npm环境变量配置

    node环境变量配置,npm环境变量配置引言:很久没有在windows上配过node,记得以前node环境变量是要加NODE_PATH到用户变量,再在系统变量引入NODE_PATH的,而npminstall的全局包目录会存放在C:/Users[用户]/administrator[你的计算机名字]/AppData/Roaming/npm目录下,而现在貌似有更高级的做法!传统方法总结:npm包全局目录:C:/Use…

  • 论坛发帖技巧_百度贴吧回复显示帖子审核中

    论坛发帖技巧_百度贴吧回复显示帖子审核中8)今天看到个帖子,想贴个回复,点个引用出来了小测验.开始的时候还没细看以为是调查,结果:cry:看表情应该知道,原来是有答案的,大部分答错,也没了逛论坛的心情.我很想知道,以最俗的免费公厕,要是说大家没用过,那我肯定不相信,一般的公厕都在入门的地方挂个牌牌,使用细则什么的,试问:有人上公厕之前认真细读过么?而…

  • 【通信系统仿真设计】基于MATLAB的直接序列扩频通信系统仿真

    【通信系统仿真设计】基于MATLAB的直接序列扩频通信系统仿真直接扩频序列调制是用速率很高的伪噪声码序列与信息码序列模二相加(波形相乘)后得到复合码序列,用复合码序列去控制载波相位,从而获得直接扩频序列信号的。直接扩频通信具有低截获概率、抗干扰能力强以及易于实现码分多址等优点,在抗干扰通信及民用移动通信中都得到了广泛的应用。

  • 数据库系列之TiDB存储引擎TiKV实现机制

    数据库系列之TiDB存储引擎TiKV实现机制TiDB存储引擎TiKV是基于RocksDB存储引擎,通过Raft分布式算法保证数据一致性。本文详细介绍了TiKV存储引擎的实现机制和原理,加深对TiDB底层存储架构的理解。

  • 良心推荐,我珍藏的一些Chrome插件[通俗易懂]

    良心推荐,我珍藏的一些Chrome插件[通俗易懂]上次搬家的时候,发了一个朋友圈,附带的照片中不小心暴露了自己的Chrome浏览器插件之多,于是就有小伙伴评论说分享一下我觉得还不错的浏览器插件。我下面就把我日常工作和学习中经常用到的一些Chrome浏览器插件分享给大家,随便一个都能提高你的“生活品质”和工作效率。MarkdownHereMarkdownHere可以让你更愉快的写邮件,由于支持Markdown直接转电子邮…

  • HTML空格标记_html换行标记

    HTML空格标记_html换行标记HTML6种空格标记HTML提供了5种空格实体(spaceentity),它们拥有不同的宽度,非断行空格(&nbsp;)是常规空格的宽度,可运行于所有主流浏览器。其他几种空格(&ensp;&emsp;&thinsp;&zwnj;&zwj;)在不同浏览器中宽度各异。&nbsp;它叫不换行空格,全称No-BreakSpace,它是最常见和我们使用最多的空格,大多数的人可能只接触了&nbsp;,它是按下space键产生的空格。在HTM

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号