import math
分解结果 = dict()
已知素数 = [2, 3]
当前素数序号 = 0
def getPrime(待分解数: int) -> str:
global 分解结果, 已知素数, 当前素数序号
assert isinstance(待分解数, int)
assert 待分解数 > 1
def 判断素数(_判断所用因数们: list, _待判断数: int):
_待判断数平方根 = math.floor(math.sqrt(_待判断数))
for _当前因数 in _判断所用因数们:
if _待判断数 % _当前因数 == 0:
return False # 不是素数
elif _当前因数 > _待判断数平方根:
return True # 是素数
def 更新素数表():
_下一个素数 = 已知素数[-1]+2
while not 判断素数(已知素数, _下一个素数):
_下一个素数 += 2
已知素数.append(_下一个素数)
return
def 递归处理(待分解因数: int) -> None: # **这一次**待分解的数字
global 当前素数序号
待分解因数平方根 = math.floor(math.sqrt(待分解因数)) # 待分解的数字的平方根
当前素数 = 已知素数[当前素数序号] # 取一个素数
print(f'{待分解因数}分解开始')
print(f'当前素数：{当前素数}')
if 待分解因数 == 1: # 乘以一不用写了，乘不乘没区别
print(f'当前无需分解，分解结果：{分解结果}')
return
# (*)
if 待分解因数 == 当前素数: # 待分解的数就是这次的素数，直接算进去
print(f'{待分解因数}就是当前素数，加入分解结果')
if 待分解因数 in 分解结果:
分解结果[待分解因数] += 1
else:
分解结果.update({待分解因数: 1})
return
if not 待分解因数 % 当前素数:
print(f'可以直接用{当前素数}分解{待分解因数}进行递归')
else:
print(f'更新素数以后才能找到分解{待分解因数}的方法或者确定它是素数')
while 待分解因数 % 当前素数: # 待分解的数字不能被当前素数整除
# 如果某因数在待分解数中的指数大于一
# 当待分解数从最小的素数开始分解
# 会先除到剩下某因数的N次方的倍数
# 当某因数以下的素数都被分解出去了
# 某因数成为最小的素数
# 因此当前素数会一直走到某因数
# 此时不满足循坏条件，直接退出循环，进行递归处理。
# 然后这个递归处理会分别处理某因数，和某因数的N-1次方的倍数
# 而此时当前素数已经走到某因数了！
# 因此，指数大于一的因数不会再(#)被加入！！！
if 当前素数 > 待分解因数平方根: # (#)
print(f'当前素数大于待分解因数平方根，{待分解因数}直接加入分解结果')
# 待分解因数不能被此前的任何素数整除
# 甚至此时当前素数也没有走到待分解因数
# 因此待分解因数此前没有被从(*)加入
# 而当前素数没有走到待分解因数，就说明递归处理中没有处理过“待分解因数的平方的倍数”
# 就说明待分解因数在待分解数中的指数为一
分解结果.update({待分解因数: 1})
return
else:
# 取一个新的素数
当前素数序号 += 1
if 当前素数序号 == len(已知素数):
更新素数表()
当前素数 = 已知素数[当前素数序号]
print(f'更新当前素数：{当前素数}')
递归处理(当前素数) # 递归处理的就是当前素数，所以直接在(*)加入，后面的操作都不会进行
递归处理(待分解因数//当前素数) # 接着分，最后就是把最后一个（最大的一个）素因数分解出去以后这边就是1，然后这个函数就该一层层return出去了
print(f'{待分解因数}分解完毕')
递归处理(待分解数)
res = f'{待分解数}={"*".join([f"{k}^{v}^" for k, v in 分解结果.items()])}'
res = res.replace('*', '\\*').replace('^1^', '')
分解结果.clear()
当前素数序号 = 0
return res
print(getPrime(36))
