当前位置:网站首页>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)
边栏推荐
猜你喜欢
随机推荐
Shell编程之正则表达式
SSM整合开发案例
.net(一)WebService创建
Record a failure to upgrade the client's APP database version number
JS基础1
IP地址及子网划分
传输层协议介绍
Win10桌面图标排列混乱
DIMP:Learning Discriminative Model Prediction for Tracking 学习判别模型预测的跟踪
生成对抗网络GAN:Generative Adversarial Networks
实现弹簧柔性状态的2种方式 | Solidworks教程
三层交换机原理及配置
Kotlin Coroutines - Exception Handling
[STL]list
Luogu P1110 report statistics multiset stl good question
如何生成dll文件 采用VS2017生成dll文件(动态库文件)和lib文件(静态库文件)以C语言为例
【机器学习】支持向量机(SVM)代码练习
SQL存储过程
Oracle 限制时将空值排除
pip安装更换镜像