python求质数的3种方法
作者:z大酱 时间:2023-02-12 04:07:54
本文为大家分享了多种方法求质数python实现代码,供大家参考,具体内容如下
题目要求是求所有小于n的质数的个数。
求质数方法1:
穷举法:
根据定义循环判断该数除以比他小的每个自然数(大于1),如果有能被他整除的就不是质数:
def countPrimes1(self, n):
"""
:type n: int
:rtype: int
"""
if n<=2:
return 0
else:
res=[]
for i in range(2,n):
flag=0 # 质数标志,=0表示质数
for j in range(2,i):
if i%j ==0:
flag=1
if flag==0:
res.append(i)
return len(res)
求质数方法2:
利用定理:如果一个数是合数,那么它的最小质因数肯定小于等于它的平方根。所以判断一个数是否是质数,只需判断它是否能被小于它开根后的所有数整除。这样做的运算会少很多。
def countPrimes2(self, n):
if n<=2:
return 0
else:
res=[]
for i in range(2, n):
flag=0
for j in range(2, int(math.sqrt(i))+1):
if i % j == 0:
flag = 1
if flag == 0:
res.append(i)
return len(res)
求质数方法3:
利用定理:如果一个数是合数,那么它的最小质因数肯定小于等于它的平方根。我们可以发现只要尝试小于等于平方根的所有数即可。列举从 3 到根号x的所有数,还是有些浪费。比如要判断101是否质数,101的根号取整后是10,需要尝试的数是1到10。但是可以发现,对9的尝试是多余的。不能被3整除,必然不能被9整除……顺着这个思路走下去,其实,只要尝试小于根号x的质数即可。而这些质数,恰好前面已经算出来了,已经存在res中了。
def countPrimes3(self, n):
if n <= 2:
return 0
else:
res = []
for i in range(2, n):
flag = 0
for j in res:
if i % j == 0:
flag = 1
if flag == 0:
res.append(i)
return len(res)
来源:https://blog.csdn.net/zhangwei15hh/article/details/78471593
标签:python,质数
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
浅谈redux, koa, express 中间件实现对比解析
2024-05-02 16:28:05
![](https://img.aspxhome.com/file/2023/8/130488_0s.jpg)
mysql mysqldump只导出表结构或只导出数据的实现方法
2024-01-23 19:46:55
php pdo oracle中文乱码的快速解决方法
2023-11-16 22:12:47
Linux下mysql5.6.24(二进制)自动安装脚本
2024-01-21 12:36:42
mysql 超大数据/表管理技巧
2024-01-16 22:14:05
MySQL异常处理浅析
2024-01-17 21:47:44
Windows下安装python2.7及科学计算套装
2023-05-28 13:35:19
![](https://img.aspxhome.com/file/2023/9/125009_0s.png)
Python selenium环境搭建实现过程解析
2023-10-06 06:18:48
![](https://img.aspxhome.com/file/2023/1/63271_0s.png)
Python容器类型公共方法总结
2022-06-24 23:58:06
asp中数组的用法
2008-05-12 22:29:00
js 仿Photoshop鼠标滚轮控制输入框取值(修正兼容Chrome)
2010-02-05 12:27:00
使用xml http为网站增加域名查询功能
2008-05-29 13:42:00
python爬取”顶点小说网“《纯阳剑尊》的示例代码
2021-02-14 11:03:35
![](https://img.aspxhome.com/file/2023/4/105074_0s.png)
使用Python做定时任务及时了解互联网动态
2021-07-08 17:54:16
![](https://img.aspxhome.com/file/2023/6/104966_0s.png)
Python实现npy/mat文件的保存与读取
2023-07-22 08:49:48
![](https://img.aspxhome.com/file/2023/8/83738_0s.png)
vue.js默认路由不加载linkActiveClass问题的解决方法
2024-05-02 16:53:25
![](https://img.aspxhome.com/file/2023/3/130153_0s.png)
Python实现账号密码输错三次即锁定功能简单示例
2023-07-22 07:40:21
通过自定义字段重新排序 WordPress 文章方法
2023-12-14 21:52:53
![](https://img.aspxhome.com/file/2023/4/132394_0s.jpg)
CentOS 7.6安装MySQL 5.7 GA版的教程图解
2024-01-27 11:47:48
![](https://img.aspxhome.com/file/2023/7/118247_0s.png)
python中列表的切片与修改知识点总结
2023-08-29 00:49:08
![](https://img.aspxhome.com/file/2023/4/84094_0s.jpg)