当前位置:网站首页>204. Count Primes
204. Count Primes
2022-08-09 07:57:00 【scwMason】
Count the number of prime numbers less than a non-negative number, n.
Example:
Input: 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
就是寻找比n小的素数有多少个
这里我们用了素数筛的方法,将时间复杂度降到线性时间,素数筛基本思想就是一个素数的倍数一定不是素数
易懂版本:
class Solution:
def countPrimes(self, n: int) -> int:
ispri=[0,0]+[1]*(n-2)
if n==0 or n==1:
return 0
for i in range(2,int(n**0.5)+1):
if ispri[i]:
for j in range(i*i,n,i):
ispri[j]=0
return sum(ispri)
巧用list运算符,结果稍许提高了一些运算时间
def countPrimes(self, n: int) -> int:
ispri=[0,0]+[1]*(n-2)
if n==0 or n==1:
return 0
for i in range(2,int(n**0.5)+1):
if ispri[i]:
ispri[i**2::i]=[0]*(len(ispri[i**2::i]))
return sum(ispri)
边栏推荐
猜你喜欢
随机推荐
“互联网+”大学生创新创业大赛经历
oracle权限问题
C语言笔记 学习预处理 学习宏定义
RestFul,会话技术,Fiddler
yolov5检测数据集标签数量
.net(三) 项目结构
原生JDBC操作数据库
Forest Program DFS + tanjar cactus
【无标题】
[STL]stack与queue
生成对抗网络GAN:Generative Adversarial Networks
RAID配置实战
[STL]string
C#高级学习1
2042. 检查句子中的数字是否递增
C#基础学习
9.进程和计划任务管理(1)
弹性盒样式、移动端、VW适配、响应式布局
resourcemanager启动失败,别的节点成功
ncnn 推理猫狗识别