前情介绍
今天遇到一个需求：找到一个数所有的质因数。
初步解决
先定义一个判断质数的函数：
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 += 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以外，两个没有其他共同质因子的正整数称为互质。
因为1没有质因子，1与任何正整数（包括1本身）都是互质。
正整数的因数分解可将正整数表示为一连串的质因子相乘，质因子如重复可以用指数表示。
根据算术基本定理，任何正整数皆有独一无二的质因子分解式。只有一个质因子的正整数为质数。 请在这里输入引用内容 每个合数都可以写成几个质数（也可称为素数）相乘的形式，这几个质数就都叫做这个合数的质因数。如果一个质数是某个数的因数，那么就说这个质数是这个数的质因数；而这个因数一定是一个质数。
具体请查看什么是质因数，质因数（素因数或质因子）在数论里是指能整除给定正整数的质数-CSDN博客文章浏览阅读3.4k次，点赞2次，收藏4次。每个合数都可以写成几个质数（也可称为素数）相乘的形式，这几个质数就都叫做这个合数的质因数。如果一个质数是某个数的因数，那么就说这个质数是这个数的质因数；16=2×2×2×2,2就是16的质因数，把一个合数写成几个质数相乘的形式表示，这也是分解质因数。正整数的因数分解可将正整数表示为一连串的质因子相乘，质因子如重复可以用指数表示。什么是质因数，质因数（素因数或质因子）在数论里是指能整除给定正整数的质数。质因数（素因数或质因子）在数论里是指能整除给定正整数的质数。只有一个质因子的正整数为质数。......https://blog.csdn.net/Hodors/article/details/126038749#:~:text=%E8%B4%A8%E5%9B%A0%E6%95%B0%EF%BC%88%E7%B4%A0%E5%9B%A0%E6%95%B0%E6%88%96%E8%B4%A8%E5%9B%A0%E5%AD%90%EF%BC%89%E5%9C%A8%E6%95%B0%E8%AE%BA%E9%87%8C%E6%98%AF%E6%8C%87%E8%83%BD%E6%95%B4%E9%99%A4%E7%BB%99%E5%AE%9A%E6%AD%A3%E6%95%B4%E6%95%B0%E7%9A%84%E8%B4%A8%E6%95%B0%E3%80%82%20%E9%99%A4%E4%BA%861%E4%BB%A5%E5%A4%96%EF%BC%8C%E4%B8%A4%E4%B8%AA%E6%B2%A1%E6%9C%89%E5%85%B6%E4%BB%96%E5%85%B1%E5%90%8C%E8%B4%A8%E5%9B%A0%E5%AD%90%E7%9A%84%E6%AD%A3%E6%95%B4%E6%95%B0%E7%A7%B0%E4%B8%BA%E4%BA%92%E8%B4%A8%E3%80%82,%E5%9B%A0%E4%B8%BA1%E6%B2%A1%E6%9C%89%E8%B4%A8%E5%9B%A0%E5%AD%90%EF%BC%8C1%E4%B8%8E%E4%BB%BB%E4%BD%95%E6%AD%A3%E6%95%B4%E6%95%B0%EF%BC%88%E5%8C%85%E6%8B%AC1%E6%9C%AC%E8%BA%AB%EF%BC%89%E9%83%BD%E6%98%AF%E4%BA%92%E8%B4%A8%E3%80%82%20%E6%AD%A3%E6%95%B4%E6%95%B0%E7%9A%84%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3%E5%8F%AF%E5%B0%86%E6%AD%A3%E6%95%B4%E6%95%B0%E8%A1%A8%E7%A4%BA%E4%B8%BA%E4%B8%80%E8%BF%9E%E4%B8%B2%E7%9A%84%E8%B4%A8%E5%9B%A0%E5%AD%90%E7%9B%B8%E4%B9%98%EF%BC%8C%E8%B4%A8%E5%9B%A0%E5%AD%90%E5%A6%82%E9%87%8D%E5%A4%8D%E5%8F%AF%E4%BB%A5%E7%94%A8%E6%8C%87%E6%95%B0%E8%A1%A8%E7%A4%BA%E3%80%82
完结撒花
可以看出，这个相对来说很基础，之所以记录下来是因为对【后面的“ + 1 ”必须有】的思考，为什么需要 + 1 呢？其实很简单，不加就会把平方根下的这个因数给遗漏掉，导致把一个🈴数误判为质数，这是不允许的。