python:整数分解成质因数乘积形式

转载请注明原作者 @yoshino(简书)
很简单的一道算法题,但是很多同学写了一堆循环,不是很好理解。闲来无事自己撸了一遍。直接上代码,很好理解


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def (x):#判断一个数是不是质数
for i in range(2, x - 1):
if (x % i == 0):
return 0
else:
continue
return 1
def fen(x):#将输入数字作因数分解,得到质因数和剩余值
for i in range(2, x - 1):
if (x % i == 0):
if (ju(i) == 1):
return i, x / i
return 1, x
k = input()
print k, '=',
cheng, yu = fen(k)
while (cheng != 1):
print cheng, '*',
cheng, yu = fen(yu)
print yu