如何找到一个数的所有质因数,以及如何快速判断一个数是不是质数 | 您所在的位置:网站首页 › 226的因数 › 如何找到一个数的所有质因数,以及如何快速判断一个数是不是质数 |
前情介绍
今天遇到一个需求:找到一个数所有的质因数。 初步解决先定义一个判断质数的函数: def is_Prime(number): i = 2 count = 0 while i < number: if number % i == 0 : count += 1 i += 1 if count > 0: return False else: return True接着定义一个寻找质因数的函数: def find_Prime_Factor(number): i = 2 while i < number + 1: if(number % i == 0): if is_Prime(i): print(i , end=" ") i += 1ok ,搞定了 进一步分析这个程序可以是可以,但是至少有两处可以改进的地方: 首先,判断质数要遍历到number,也就是时间复杂度为O(n),通过改变while循环的条件可以把遍历数目变为number/2,时间复杂度记为O(n/2)【其实时间复杂度还是O(n)】: while i < number // 2 + 1: 然后,记得之前有一个方法是遍历到平方根就可以了,这个时候只需要遍历到 在这里需要说明的两点: 1、必须要把平方根取整 2、后面的“ + 1 ”必须有 最后,质数判断基本已经到了最极限的水平了,当然可能还有更好的,笔者没学习到,如果有大佬,欢迎补充。 那就是求因数需要优化了,这个时候参考上面求质数的过程,我们是否也可以通过这几方面来求呢?答案是肯定的,在此附上快速求一个数所有因数的代码: def find_factors(num): factors = [] for i in range(1, int(num ** 0.5) + 1): if num % i == 0: factors.append(i) if num // i != i: factors.append(num // i) factors.sort() return factors整合到找质因数的函数也比较容易: def find_Prime_Factor(number): i = 2 # while i < number + 1: while i < int(number ** 0.5) + 1: if(number % i == 0): if is_Prime(i): print(i, end=" ") if num // i != i: if is_Prime(num // i): print(num // i , end=" ") i += 1 延伸阅读1、什么是质因数 质因数(素因数或质因子)在数论里是指能整除给定正整数的质数。 除了1以外,两个没有其他共同质因子的正整数称为互质。 因为1没有质因子,1与任何正整数(包括1本身)都是互质。 正整数的因数分解可将正整数表示为一连串的质因子相乘,质因子如重复可以用指数表示。 根据算术基本定理,任何正整数皆有独一无二的质因子分解式。只有一个质因子的正整数为质数。 请在这里输入引用内容 每个合数都可以写成几个质数(也可称为素数)相乘的形式,这几个质数就都叫做这个合数的质因数。如果一个质数是某个数的因数,那么就说这个质数是这个数的质因数;而这个因数一定是一个质数。 具体请查看什么是质因数,质因数(素因数或质因子)在数论里是指能整除给定正整数的质数-CSDN博客文章浏览阅读3.4k次,点赞2次,收藏4次。每个合数都可以写成几个质数(也可称为素数)相乘的形式,这几个质数就都叫做这个合数的质因数。如果一个质数是某个数的因数,那么就说这个质数是这个数的质因数;16=2×2×2×2,2就是16的质因数,把一个合数写成几个质数相乘的形式表示,这也是分解质因数。正整数的因数分解可将正整数表示为一连串的质因子相乘,质因子如重复可以用指数表示。什么是质因数,质因数(素因数或质因子)在数论里是指能整除给定正整数的质数。质因数(素因数或质因子)在数论里是指能整除给定正整数的质数。只有一个质因子的正整数为质数。...... 可以看出,这个相对来说很基础,之所以记录下来是因为对【后面的“ + 1 ”必须有】的思考,为什么需要 + 1 呢?其实很简单,不加就会把平方根下的这个因数给遗漏掉,导致把一个🈴数误判为质数,这是不允许的。 |
CopyRight 2018-2019 实验室设备网 版权所有 |