程序员自学网站,免费logo商标设计软件,内部网站 建设方案,网络营销是什么的具体应用前情介绍 今天遇到一个需求#xff1a;找到一个数所有的质因数。
初步解决 先定义一个判断质数的函数#xff1a;
def is_Prime(number):i 2count 0while i number:if number % i 0 :count 1i 1if count 0:return Falseelse:return True 接着定义一个寻找质…前情介绍 今天遇到一个需求找到一个数所有的质因数。
初步解决 先定义一个判断质数的函数
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 1ok 搞定了
进一步分析 这个程序可以是可以但是至少有两处可以改进的地方 首先判断质数要遍历到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 呢其实很简单不加就会把平方根下的这个因数给遗漏掉导致把一个数误判为质数这是不允许的。
