python,算法训练 分解质因数

详情思路在后面代码中的注释,核心思路是：

1.先用一个数组将不大于b的所有质数保存如[3,10],数组为[2,3,5,7]

2.如果这个[a，b]中值本身就是素数，说明不能被1和本身以外的数约，直接返回本身，即7=7

3.再写一个dfs函数，判断质数数组中的元素是否为[a，b]中值的约数

4.如果是约数，则再考虑经过最小约数后的值，是否还可以再约数，是就再进行约。

dfs(8/2)=dfs(4),即8 = 2*4,4 = 2*2,即8 = 2*2*2

详情在后面代码中的注释，尽量细致的注释上去了。

#输入a,b的值作为范围
a,b = (int(x) for x in input().split())#用一个zhishu，质数数组保存所有的素数,且这个素数在不大于b的范围内（可以小于a）
z = []
for i in range(2,b+1):#开始遍历值flag = 0for j in range(1,int(i/2)+1):#看这些值是否为质数，这里有一个技巧因为一个数不会被大于自己一半整除，当然不用这个技巧也不会超时间if j != 1 and int(i) % j == 0:#是否为素数，不是素数标记为flag=1flag = 1;breakif flag == 0:#如果没有被标记，说明是素数，只能被1和自己整除z.append(i)#加入质数数组#用一个深度查看函数，如有例子8 = 2 * 4，然后将dfs(8/2),即将4又做一次分解，得8=2*2*2
def dfs(k):if k <= 1:#如果不能分解了，说明k=1了，即4分解为2*2,dfs(2/2)=dfs(1),1不能分解直接返回print()#这里为了格式打印一个换行符return;#遍历z质数数组for x in z:#如果k除以质数数组的值没有余数，说明可以除if k >= x and k % x == 0:print('*',x,sep='',end='')#加入这个x值，即加入例子的2dfs(k/x)#然后继续递归dfs(8/2)=dfs(4),再把4进行分解breakreturn;
#遍历a到b之间的整数
for i in range(a,b+1):print(i,'=',sep='',end='')#维持题目格式if i in z:#如果i本身就是素数，说明不能被1和本身以外的数约，直接返回本身print(i)else:#否则开始对这个i进行分解操作，如8for x in z:#遍历质数数组------1if i >= x and i % x == 0:#看8 % [2,3,5,7]print(x,sep='',end='')#找到一个8%2=0,故加入2这个约数dfs(i/x)#继续看dfs(8/2)即dfs(4)可以分解不，传入dfs数组--4break#说明这里为什么没有把1-4这些语句用一个dfs代替，为了统一输出格式否则出现#8 = *2*2*2 或者 8 = 2*2*2*，当然笔者有更好的方法，可以在评论讨论一下