如何找到一个数的所有质因数，以及如何快速判断一个数是不是质数

news/2024/5/9 14:35:24/文章来源:https://blog.csdn.net/BetrayFree/article/details/132390228

前情介绍

今天遇到一个需求：找到一个数所有的质因数。

初步解决

先定义一个判断质数的函数：

def is_Prime(number):i = 2count = 0while i < number:if number % i == 0 :count += 1i += 1if count > 0:return Falseelse:return True

接着定义一个寻找质因数的函数：

def find_Prime_Factor(number):i = 2while i < number + 1:if(number % i == 0):if is_Prime(i):print(i , end=" ")i += 1

ok ，搞定了

进一步分析

这个程序可以是可以，但是至少有两处可以改进的地方：

首先，判断质数要遍历到number，也就是时间复杂度为O(n)，通过改变while循环的条件可以把遍历数目变为number/2，时间复杂度记为O(n/2)【其实时间复杂度还是O(n)】:

while i < number // 2 + 1:

然后，记得之前有一个方法是遍历到平方根就可以了，这个时候只需要遍历到 $\sqrt{n}$ ，这个时候和上面的相比就有本质的区别了，时间复杂度为O( $\sqrt{n}$ ):

while (i < int(math.sqrt(number)) + 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