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

前情介绍

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

初步解决

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

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:

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

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

完结撒花

        可以看出，这个相对来说很基础，之所以记录下来是因为对【后面的“ + 1 ”必须有】的思考，为什么需要 + 1 呢？其实很简单，不加就会把平方根下的这个因数给遗漏掉，导致把一个🈴数误判为质数，这是不允许的。