算法:质数判断
2022/4/5 22:19:08
本文主要是介绍算法:质数判断,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
质数判断方法
一、暴力法
定义:一个只能被1和自身整除的数为质数
算法:从2开始遍历至数字本身减一,若可被其他数整除则不是质数
点击查看代码
def isPrime(x): if x==1: return False for i in range(2,x): if not x%i: return False return True
二、遍历优化
特点:任意一个非质数n,其任一因式二元组中的两个数,一个小于 \(\sqrt{n}\),另一个大于 \(\sqrt{n}\)
优化:遍历区间只需用到\(\sqrt{n}\)
点击查看代码
def isPrime(x): if x==1: return False #floor():向下取整 for i in range(2,floor(sqrt(x))+1): if not x%i: return False return True
三、深度优化
特点:质数总是等于6x-1或6x+1,其中x为自然数
即质数总是6的倍数的左右两端的数,但反之不一定(6的倍数的左右两端的数不一定是质数)
而不是6的倍数的左右两端的数一定不是质数(可证)
则优化过程是:
1. 先判断是否为6的倍数的左右两端的数,若不是,则一定不是质数
2. 以6为步长,从5开始,到 \(\sqrt{n}\),通过6x-1和6x+1来排除在6的倍数的左右两端的数中不是质数的数
因为通过第一个判断后,只剩下6的倍数的左右两端的数即6x-1和6x+1。第二个判断即判断数字n这个6的倍数的左右两端的数是否为质数。
① 对于循环中6i-1,6i,6i+1,6i+2,6i+3,6i+4,其中如果n能被 6i,6i+2,6i+4整除,则n至少得是一个偶数,但是(n=6x-1或6x+1)的形式明显是一个奇数,
故不成立,因此判断时不需用这三种数。
② 对于6i+3,因为可被3整除,若n可以整除6i+3则n也为3的倍数,但n=6x-1或6x+1,n必不为3的倍数,因此也不用该数
③ 则最终剩下6i-1和6i+1,判断二者是否为n的除数即可。下面程序中i从5开始,则表示6i-1,则6i+1为i+2
点击查看代码
def isPrime(n): if n==2 or n==3: return True #不是6的倍数的左右两端的数一定不是质数 if n==1 or (n%6!=1 and n%6!=5): return False #判断6的倍数的左右两端的数是否为质数 for i in range(5,floor(sqrt(n))+1)[::6]: if not n%i or not n%(i+2): return False return True
这篇关于算法:质数判断的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性