<LeetCode天梯>Day043 计数质数(埃拉托斯特尼筛法) | 初级算法 | Python_府学路18号车神的博客-程序员秘密

技术标签: 埃拉托斯特尼筛法  算法  python  LeetCode天梯  leetcode  

作者简介:大家好,我是车神哥,府学路18号的车神
About—>车神:从寝室实验室快3分钟,最慢3分半(那半分钟其实是等绿
个人主页:应无所住而生其心的博客_府学路18号车神_程序员秘密
点赞评论收藏 == 养成习惯(一键三连
本系列主要以刷LeetCode力扣)网站的各类题为标准,实现自我能力的提升为目标
希望大家多多支持~一起加油

其他专栏

周五了,怎么就又到周末了啊!~,一个周感觉啥也没干就又过去了,哎,时间管理有问题啊还是事情真的太多,导致一件事都没有做好,这搞得,ToDo list每天都在做的还是做不完,ddl天天催,还是那样,真希望能专心的做做自己想要的事情!哎,坚持吧,熬过去就好了!

每天进步一点点,就已经很棒很棒了,坚持坚持,不要太累,拒绝内卷,从每日一练开始,每天十分钟,快乐生活一辈子!疫情依旧反复,大家带好口罩啊~ 继续继续,来,今天和车神哥一起来提升自己的Python编程面试能力吧,刷天梯~

放上我拍的Photo吧!

在这里插入图片描述

每日推荐一首歌:平凡之路——朴树

以下为我的天梯积分规则

每日至少一题:一题积分+10分
若多做了一题(或多一种方法解答),则当日积分+20分(+10+10)
若做了三道以上,则从第三题开始算+20分(如:做了三道题则积分-10+10+20=40;做了四道题则积分–10+10+20+20=60


初始分为100分
若差一天没做题,则扣积分-10分(周六、周日除外注:休息
坚持!!!


初级算法

刷题目录

数学

在这里插入图片描述

题干

统计所有小于非负整数 n 的质数的数量。

示例1:

输入:n = 10
输出:4
解释:小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例2:

输入:n = 0
输出:0

示例3:

输入:n = 1
输出:0


埃拉托斯特尼筛法

这道题,我们只需要知道质数是什么?

质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。

解决此法的方法有:枚举 < 埃氏筛 < 欧式筛(线性筛) < 奇数筛

不过掌握埃拉托斯特尼法,已经完全足够了!~

“埃拉托斯特尼筛法,简称埃氏筛或爱氏筛,是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数,必须把不大于根号n的所有素数的倍数剔除,剩下的就是素数。”

class Solution:
    def countPrimes(self, n: int) -> int:
        isNumPrimes = [True] * n    # 将所有数展开,且标记质数为真
        count = 0  # 设置计数器

        for x in range(2, n):
            if isNumPrimes[x]:
                count += 1
                # 使用埃氏筛,将合数去除
                for y in range(x*2, n, x):   # 遍历x*2, 开始,结束n,步长x
                    isNumPrimes[y] = False
        return count

在这里插入图片描述
今日到处结束,继续改论文,卷起来!~

Reference

作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xngt85/
来源:力扣(LeetCode)


今日得分:+10
总得分:840

加油!!!

坚持读Paper,坚持做笔记,坚持学习,坚持刷力扣LeetCode!!!
坚持刷题!!!打天梯!!!
To Be No.1


创作不易,过路能关注收藏点个赞三连就最好不过了

ღ( ´・ᴗ・` )


到底是孤独的人强大,还是强大的人孤独。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_44333889/article/details/121855088

智能推荐

Linux 内核延时函数_与时俱进2014的博客-程序员秘密_linux内核延时

linux内核提供3个函数分别进行纳秒,微妙和毫秒延时:void ndelay(unsigned long nsecs);void udelay(unsigned long usecs);void mdelay(unsigned long msecs);这3个函数的延时原理是忙等待,也就是说在延时的过程中并没有放弃cpu,根据cpu的频率进行一定次数

LeakCanary:检测所有的内存泄露_傲慢的上校的博客-程序员秘密

本文译自:https://corner.squareup.com/2015/05/leak-canary.html(LeakCanary是由Square公司刚刚开源用于查找Android内存泄露的库) java.lang.OutOfMemoryError at android.graphics.Bitmap.nativeCreate(Bitmap.java:-2)

ProcessingJS介绍_赶路人儿的博客-程序员秘密_processing.js

最近由于工作的关系,好好研究了一下ProcessingJS。Processing是一门可视化编程语言,ProcessingJS是它的JavaScript实现,使用HTML5的canvas,配合现代浏览器来实现web客户端的可视化技术。(不得不说,John Resig真是个高产的作者,jQuery、Sizzle、ProcessingJS)ProcessingJS做了这两件事:1.把基于Jav...

Java基础第十八课(GUI图形用户界面)_周秃秃的博客-程序员秘密

前面我们一直都是用控制台进行信息的输入输出来写Java程序但是我们平常见到的程序都是有好看的界面的你可能会想难道Java不能做界面???放心,Java可以说是很强大的它是可以做出来的,只不过用Java写Windows窗口程序都太麻烦了所以用Java来写的不多但是我还是要讲一下滴好啦 开始一、简介及简单演示我们平时电脑用的软件能看到的界面其实就是GUI(Graphic User I...

USB xHCI控制器使用总结_静思心远的博客-程序员秘密_usb xhci

USB xHCI控制器使用总结1 Intel USB xHCI控制器1.1 驱动架构1.2 x86 OTG架构1.3 x86 xHCI Scheduler Async Delay1.4 Interrupt on Short Packet1.5 x86 USB DCI DbC调试技术1.6 reset USB device1.7 PIPE PHY数据线宽度2 Bulk传输速度计算3 xHCI HS眼图调试3.1 EHCI眼图调试寄存器设置流程3.2 xHCI每个port的4个寄存器3.3 xHCI HS眼图调

itop4412 linux-4.14.2 can设备树_cuihongqiang的博客-程序员秘密

待验证&amp;pinctrl_1 { mcp2515_irq: mcp2515-irq { samsung,pins = "gpx0-1"; samsung,pin-function = &lt;EXYNOS_PIN_FUNC_INPUT&gt;; samsung,pin-pud = &lt;EXYNOS_PIN_PULL_NONE&gt;; samsung,pin-drv = &lt;EXYNOS4_PIN_DRV_LV1&gt;; };};&amp;spi_2 { num

随便推点

云客Drupal源码分析之缓存系统Cache_u011474028的博客-程序员秘密

在介绍drupal8的缓存系统前我们先了解一下缓存系统的本质及特性,缓存的存在依赖于两个目的:节省资源和提高速度,起不到这两作用则缓存没有存在的必要,当一个结果需要进行大量计算才能得到,而它又不会频繁更新那么缓存结果可以节省大量算力,缓存的是一个结果,这个结果可以存放在多台服务器上面实现负载均衡,从而进一步提高访问速度,在高访问网站中缓存非常重要,drupal8的缓存设计也是围绕这两个目的而设计。

IDEA新建项目时,没有Spring Initializr选项_BedrockOfAI的博客-程序员秘密

  版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u012860950/article/details/76146072最近开始使用IDEA作为开发工具,然后也是打算开始学习使用spring boot。看着博客来进行操作上手spring boot,很多都是说创建一个新项目(Create New Project)选择 Spring...

jmeter实现多个请求并行执行,验证线程安全_我心依依旧的博客-程序员秘密_jmeter多个请求同时并发

最近有线上发现一个bug:多个业务场景并行请求,出现下发结果存在串的现象。一、现象描述如下图所示:两个不同策略出现串的情况二、压测原理新建测试计划时有个独立运行每个线程组选项1、勾选独立运行每个线程组选项(Run Thread Groups consecutively(i.e.one at time)),则表示顺序执行。顺序执行,指的是测试计划中存在多个线程组时,第一个线程组执行完后再...

scala mysql连接池_scala实现数据库的连接池(mysql数据库,scala-2.10.4)_weixin_40005437的博客-程序员秘密

使用jdbc提供的驱动进行连接数据库。首先需要从MySQL官网上下载jdbc的驱动,得到.jar文件,这就是我们需要的jdbc驱动。 我们需要连接数据库,就首先需要我们电脑上有MySQL的数据库,并建立一个表,来存放数据。这里我自己建立一个名为mydb的表。 建立好表后一、编写实现代码类:MySqlPoolpackage test.testConnectionPollimport java.sq...

Zeroc Ice C++小例子_tangchuanhui的博客-程序员秘密

初衷是想用C++写一个服务端,在html中嵌入js调用这个服务,但是尝试了很久都没有成功。先把C++实现服务端和客户端的过程写下来。一. Ice的安装:服务端和客户端都需要安装按照官网上的例子执行命令:https://zeroc.com/downloads/ice#linux二. 定义Ice接口://// Copyright (c) ZeroC, Inc. All ri...