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)


相关推荐

  • 已知最大公约数和最小公倍数_7和15的最大公因数和最小公倍数

    已知最大公约数和最小公倍数_7和15的最大公因数和最小公倍数7-4 最大公约数和最小公倍数 (20分) 本题要求两个给定正整数的最大公约数和最小公倍数。输入格式: 输入在一行中给出两个正整数M和N(≤1000)。输出格式: 在一行中顺序输出M和N的最大公约数和最小公倍数,两数字间以1空格分隔。 输入样例: 511 292 输出样例: 73 2044#include <iostream>#include<ioma…

  • 最全综述 | 医学图像处理「建议收藏」

    0、引言医学图像处理的对象是各种不同成像机理的医学影像,临床广泛使用的医学成像种类主要有X-射线成像(X-CT)、核磁共振成像(MRI)、核医学成像(NMI)和超声波成像(UI)四类。…

  • js中换行_input怎么不换行

    js中换行_input怎么不换行”\n”为换行转移符,注意\n前后的空格!!!varname=$(“#name”);varname=”姓名:”+name+”\n”;2020年1月补充:一年前的文章,现在忘了当时换行是为了干什么,好像是弹出框消息太长,会自动换行。但是希望一句一句的换行。自动换行效果:\n换行效果:<!DOCTYPEhtml><…

    2022年10月28日
  • Marlin2.0.9 Configuration_adv.h详解

    Marlin2.0.9 Configuration_adv.h详解/**Marlin3DPrinterFirmwareCopyright©2020MarlinFirmware[https://github.com/MarlinFirmware/Marlin]BasedonSprinterandgrbl.Copyright©2011CamielGubbels/ErikvanderZalmThisprogramisfreesoftware:youcanredistributeitand/ormodif

  • Protecting World Leaders Against Deep Fakes(CVPR 2020)

    Protecting World Leaders Against Deep Fakes(CVPR 2020)文章目录IntroductionInnovationMethodExperimentProtectingWorldLeadersAgainstDeepFakes(CVPR2020)paperPDFIntroduction深度学习的应用促使了人脸伪造技术的巨大进步。现有AI-合成的人脸伪造方式可以分为以下三种:faceswap:将视频中出现的人脸替换为其他人的脸,一般对整个面部进行对齐和替换lip-sync:使得视频中的人物口型按照既定音频变化,一般仅伪造目标的唇部区域pupp

  • python版DDOS攻击工具脚本

    python版DDOS攻击工具脚本代码中有注释说明#!/usr/bin/envpython#-*-coding:UTF-8-*-fromredisimportRedisimporttimefromgurdimport*rdb=Redis(“127.0.0.1”)vips={}defsetOffset(offset): keys=rdb.keys(“*”) min=offset forkeyinkeys: ifkey==”offset”: cont

发表回复

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

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