当前位置 博文首页 > weixin_30498921的博客:python 素因子分解
在使用python解决问题之前,我们先说一下,什么是素因子分解
所谓素因子分解就是,先找这个数的所有约数(约数即:a%b == 0,也就是a可以被b整除)
例如:20的约数集合为 [1, 2, 5, 10, 20]
那么素因子分解呢?
就是从最小的素数约数开始除,也就是这个除数要满足两个条件,一是约数,二是素数
那么这里20的最小的素约数是2,所以我们从2开始除,并且一直除到不能被整出为止:
num = 20
num = num / 2
num = 10(这里num依旧可以被2整除,所以再来一次)
num = num / 2
num = 5 (num很明显除以2不能整除)
所以接下来被除数需要向后走,即5(再取下一个数为除数之前,要先判断是否为素数,这里5为素数,如果不是素数比如4则需要继续向后取)
num = num / 5
num = 1
至此,运算结束。所以,我们得到20的素因子集合为:[2, 2, 5]
?
那么接下来就是使用python实现的部分了
通过之前的解析过程,我们可以看到我们需要这么两个小模块:
1. 判断数字是否是素数,如果数字本身是素数,那么直接返回1和它本身就可以了,因为素数不能被分解了,即 [1, num]
2. 我们需要获得这个数的所有约数,以便于我们进行作除法
下面是这两个部分的实现:
1 # 判断是否是素数 2 def isprime(num): 3 count = num / 2 4 while count > 1: 5 if num % count == 0: 6 return False 7 count -= 1 8 else: 9 return Truecs