Python第25题：分解质因数（输出 90=2×3×3×5 形式）

题目

从标准输入读入一个大于 1 的正整数 n，将其分解为质因数乘积的形式输出（例如：90=2*3*3*5）。

输入格式：一行输入一个正整数 n。

输出格式：按 n=p1*p2*...*pk 的格式输出质因数分解结果，末尾换行。

数据范围与约定：2 ≤ n ≤ 10⁹。

思路与算法

1. 试除法原理
从最小质数 d = 2 开始试除。若 n % d == 0，则 d 必为质因数，循环除尽该因数并记录，随后 d += 1。

2. 范围缩减到 √n
只需循环到 d * d <= n。循环结束后若剩余 n > 1，则说明剩下的数本身就是一个大于 √原数 的质因数，直接追加。

完整程序

n = int(input())

# 从最小质因数 2 开始试除
d = 2
factors = []
while d * d <= n:
    while n % d == 0:
        factors.append(str(d))
        n //= d
    d += 1

# 若剩余商大于 1，则本身也是一个质因数
if n > 1:
    factors.append(str(n))

print('*'.join(factors))

运行示例

输入：

90

输出：

90=2*3*3*5