分解质因数,Python
时间: 2023-03-23 17:03:48 浏览: 137
分析质因数是指将一个正整数表示为若干个质数乘积的形式,例如将60分解质因数可以得到:$60=2^2 \times 3 \times 5$。
在 Python 中,可以使用如下代码实现分解质因数的功能:
```python
def prime_factors(n):
i = 2
factors = []
while i * i <= n:
if n % i:
i += 1
else:
n //= i
factors.append(i)
if n > 1:
factors.append(n)
return factors
```
这段代码定义了一个函数 `prime_factors(n)`,接受一个正整数 `n` 作为输入,并返回一个列表,其中包含 `n` 的所有质因数。
代码的实现基于一个简单的观察:如果一个正整数 `n` 可以被一个大于1小于等于 `n` 的整数 `i` 整除,那么 `i` 必然是 `n` 的一个质因数。因此,在上述代码中,我们从2开始依次判断 `n` 是否能被 `i` 整除,如果可以,则将 `i` 添加到质因数列表中,并将 `n` 更新为 `n` 除以 `i` 的商,继续寻找下一个质因数,直到 `i*i > n`。此时如果 `n` 大于1,则说明 `n` 本身就是一个质数,也将其添加到质因数列表中。最后返回质因数列表即可。
例如,调用 `prime_factors(60)` 将返回 `[2, 2, 3, 5]`,即60的质因数分解结果。
阅读全文