36 分解质因数

每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来，叫做分解质因数。如30=2×3×5 。分解质因数只针对合数。求一个数分解质因数，要从最小的质数除起，一直除到结果为质数为止。
例如：360

需要注意的是，每次都要从最小的质数开始尝试除，例如360可以除2、除2、除2，被2整除3次才得到一个不能被2整除的45，然后再除3，除3，最后得到质数5。
如果先定义一个判定素数的函数，那么问题就变成整除和缩小问题规模了。

def isPrime(n):                            # 判断素数的函数，可以接受任意整数输入，实际上本题可以不判定2以下的数字
    if n < 2:                              # 0和1不是素数
        return False
    for i in range(2, int(n ** 0.5) + 1):  # 保证效率
        if n % i == 0:
            return False
    else:
        return True

从2开始遍历，如果数 num 能被当前数字 i 整除且当前数字 i 是素数，那就记录下当前数字i，同时将 num 变成 num // i 。

num = int(input())
ls = []
for i in range(2,num + 1):            # 2开始遍历到num
    if num % i == 0 and isPrime(i):   # 如果数 num 能被当前数字 i 整除且当前数字 i 是素数
        ls.append(i)                  # 将得到的质因数加入列表保存
        num = num // i                # 缩小 num 规模
        print(num,i)                  # 输出最后得到的num和因子i值，观察执行过程 
print(ls)                             # 输出列表中得到的质因数

测试程序
输入：360
输出：
360
180 2
60 3
12 5
[2, 3, 5]
这里会发现一个问题，2 3 5 = 30
从结果可以看到：
360 // 2 == 180
180 // 3 == 60
60 // 5 == 12
此时12已经无法被比5大的质数整除了，说明上面的算法出了问题。从上面的运算可以发现，360 // 2 的结果 180仍可以被2整除，得到的结果90仍可以被2整除……。
为了解决这个问题，可以再加一层循环，进入循环的条件是“如果数 num 能被当前数字 i 整除且当前数字 i 是素数”，这样，只有当num 不再能被 i 整除时才会退出内层循环，实现连续除运算。
代码修改如下：

num = int(input())
ls = []
for i in range(2,num + 1):                # 2开始遍历到num
    while  num % i == 0 and isPrime(i):   # 如果数 num 能被当前数字 i 整除且当前数字 i 是素数
        ls.append(i)                      # 将得到的质因数加入列表保存
        num = num // i                    # 缩小 num 规模
        print(num,i)                      # 输出最后得到的num和因子i值，观察执行过程 
print(ls)                                 # 输出列表中得到的质因数

实际上，修改的语句只有一条，原来的if 修改为while，二者的区别是：
if 只判断一次，然后就进入外层循环的下一次循环。
while 本身是循环控制语句，此语句的加入，程序从一重循环变成了二重循环，while后面的条件表达式会被重复执行，每判断结果为True就会进入内层循环一次，直至条件表达式的结果为假。
这样运算结果就变成了：
输入：
360
输出：
180 2
90 2
45 2
15 3
5 3
1 5
[2, 2, 2, 3, 3, 5]
这时可以看到分解的最终结果为2 2 2 3 3 5 1，这才是正确的分解质因数的结果。
合并上面的程序：

def isPrime(n):                           # 判断素数的函数，可以接受任意整数输入，实际上本题可以不判定2以下的数字
    if n < 2:
        return False                      # 0和1不是素数
    for i in range(2, int(n ** 0.5) + 1): # 保证效率
        if n % i == 0:
            return False
    else:
        return True                       # for 循环正常结束未遇到return时返回True
num = int(input())
ls = []
for i in range(2,num + 1):                # 2开始遍历到num
    while  num % i == 0 and isPrime(i):   # 如果数 num 能被当前数字 i 整除且当前数字 i 是素数
        ls.append(i)                      # 将得到的质因数加入列表保存
        num = num // i                    # 缩小 num 规模
print(ls)                                 # 输出列表中得到的质因数

我们知道使用筛选法，先生成小于n的所有数字，再把 2 到 sqrt(n) 之间的整数的倍数依次去掉，剩余的就是小于n的所有素数了。

结合筛选法，可以使分解质因数的程序变得更简单：

n = int(input())
ls = []
for i in range(2,n+1):   # 从2 到 n 遍历
    while(n%i == 0):     # n 可以被i整除，必是合数，将其除以i,i实际上也是按筛选法得到的素数
        ls.append(i)     # 保存得到的质因子
        n = n // i       # 缩小规模
print(ls)

可以在循环过程中减少外层循环次数：

num = int(input())
factor = []
i = 2
while num != 1:
    while num % i == 0:
        factor.append(i)
        num = num // i
        # print(num)
    i = i + 1
print(factor)
426853648526468
[2, 2, 547, 613, 971, 327757]

可以只用一层循环，用分支语句控制测试因子 i 的值：

num = int(input())
i = 2
factor = []
while i <= num:
    if num % i == 0:
        factor.append(i)
        num = num // i
    else:
        i = i + 1
print(factor)
# 2685364852646826
# [2, 3, 3, 3, 7, 197, 613, 58828097]