当前位置:网站首页>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)
边栏推荐
猜你喜欢
IDEA文件UTF-8格式控制台输出中文乱码
ImportError: cannot import name ‘imresize‘
链表专项练习(三)
SOLIDWORKS Simulation教程:计算物体的固有频率
Selenium测试案例一步步学之(2)Selenium自动测试脚本模块化(下)
一文搞懂 条件编译和预处理指令 #define、#undef、#ifdef、#ifndef、#if、#elif、#else、#endif、defined 详解
(四)BP神经网络预测(上)
C语言:打印菱形
如何把无用的代码注释为 Deprecated 弃用
Use tensorflow.keras to build a neural network model modularly
随机推荐
IDEA文件UTF-8格式控制台输出中文乱码
Use tensorflow.keras to build a neural network model modularly
3D软件开发工具HOOPS全套产品开发介绍 | HOOPS Exchange、HOOPS Communicator
一键登陆服务器脚本
VOC格式标签转YOLO格式
EXCEL uses function joint debugging (find, mid, vlookup, xlookup)
c语言位段
种子数据报错:liquibase.exception.ValidationFailedException: Validation Failed
(error) NOAUTH Authentication required.
oracle存储过程问题解答
【机器学习】支持向量机(SVM)代码练习
网络布线及数制转换
BGP路由协议的那些事?(中)
安全的Md5加密:两次加密(加盐)
账户和权限管理2
C语言:调整奇数偶数顺序
研发分享:机器学习卡片的使用
权限(下)
.net(一)WebService创建
C language: detailed explanation of soda bottle