RepentStar's Blog

世界中的一个角落

Python分解质因数递归/迭代写法

Posted on Edited on In Valine:

写这篇文章的起因是作业本上的题目
要求输入一个大于一的整数,输出形如100= 2*2*5*5的程序

原题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def f(x):
    k = 2
    flag = 0    #flag表示第一个质因数标记,不需要输出'*'
    while x != 1:
        if x % k == 0:
            if flag == 0:
                print(k, end=' ')
                ___1.___
            else:
                print('*', k, end=' ')
            ___2.___
        else:
            ___3.___

n = int(input(':'))
print(n, '= ', end="")
f(n)

原题大概长这样 ,做了一些修改

第一空

首先,这个空在flag==0的缩进体里,说明是和第一个数有关,结合上面给的注释这个题目自带的注释在作业本里真是少见呢,很容易看出这句空是为了让后面的运行跳过这段缩进,得flag=1

第二空

稍微难了那么一点点
就是说只要x % k == 0就一定要执行的代码
既然此时k已经为一个质因数了
那么要继续往下算就得让x变小所以得是x//=k
为什么非得是//？因为python里int/int得到的是float,而//得到的是int

第三空

如果x % k != 0,显而易见得,应该是k自增,所以k+=1

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def f(x):
    k = 2
    flag = 0
    while x != 1:
        if x % k == 0:
            if flag == 0:
                print(k, end=' ')
                flag = 1
            else:
                print('*', k, end=" ")
            x //= k
        else:
            k += 1

n = int(input(':'))
print(n, '= ', end="")
f(n)

递归写法

参考了CSDN文章

思路：以x % i == 0为递归条件,不满足i自增,满足则分解x再调用f(x)

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
def f(x):
    for i in range(2, x+1): 
        if x % i == 0:
            l.append(i)
            x //= i
            return f(x)


l = []
n = int(input(':'))
print(n, '= ', end="")
f(n)
print(*l, sep='*')

在参考文章的代码里有些错误,第二行的for循环range函数必须以x+1结尾,不然输入一个指数将没有输出
最后一行涉及了列表的分解和print()函数的sep参数
整个过程和递归差不多