python正整数的质因子分解。要求编写自定义函数实现该功能。例如,给定10,打印出结果:[[2,5],[1,1]],表示10=21*51;给定200,打印出结果:[[2,5],[3,2]],表示200=23*52.
时间: 2023-05-25 08:01:11 浏览: 85
python 实现分解质因数
5星 · 资源好评率100%
好的,我会扮演 ChitGPT 并回答您的问题。
下面是 Python 正整数的质因子分解的自定义函数代码实现:
```python
def prime_factors(n):
i = 2
factors = []
while i * i <= n:
if n % i:
i += 1
else:
n //= i
count = 1
while n % i == 0:
n //= i
count += 1
factors.append([i, count])
if n > 1:
factors.append([n, 1])
return factors
print(prime_factors(10)) #[[2, 1], [5, 1]]
print(prime_factors(200)) #[[2, 3], [5, 2]]
```
该函数的思路是,找到 n 的最小质数因子,记录下该质数以及其次数(即 n 可以被多少个该质数整除),然后将 n 更新为除以该质数后的商,重复以上过程,直到 n 为 1 或者无法被 i 整除(此时 i 自加1)。
例如,对于输入的 10,首先最小质数因子为 2,而 10 可以被 2 整除,我们记录下 2 x 1,然后将 10 除以 2 得到 5,继续找最小质数因子即 5,由于 5 不能被 2 整除,所以 i 自加 1,此时 i 取值为 3,由于 5 不能被 3 整除,所以 i 又自加 1,此时 i 取值为 4,由于 5 仍然不能被 4 整除,所以 i 又自加 1,此时 i 取值为 5,而 5 可以被 5 整除,我们记录下 5 x 1,然后将 5 除以 5 得到 1。此时 n 等于 1,因此分解完成,最终结果为 [[2, 1], [5, 1]],表示 10=2^1 x 5^1。
对于输入的 200,最初的最小质数因子是 2,而 200 可以被 2 整除,我们记录下 2 x 1,然后将 200 除以 2 得到 100,继续找最小质数因子即 2,由于 100 可以被 2 整除,我们记录下 2 x 2,然后将 100 除以 2 得到 50,继续找最小质数因子即 2,由于 50 可以被 2 整除,我们记录下 2 x 3,然后将 50 除以 2 得到 25,继续找最小质数因子即 5,由于 25 可以被 5 整除,我们记录下 5 x 2,然后将 25 除以 5 得到 5,继续找最小质数因子即 5,由于 5 不能被 5 整除,所以 i 自加 1,此时 i 取值为 6,由于 5 不能被 6 整除,所以 i 又自加 1,此时 i 取值为 7,由于 5 不能被 7 整除,所以 i 又自加 1,此时 i 取值为 8,由于 5 不能被 8 整除,所以 i 又自加 1,此时 i 取值为 9,由于 5 不能被 9 整除,所以 i 又自加 1,此时 i 取值为 10,而 5 仍然不能被 10 整除,所以 i 又自加 1,此时 i 取值为 11,而 5 仍然不能被 11 整除,所以 i 又自加 1,此时 i 取值为 12,而 5 仍然不能被 12 整除,所以 i 又自加 1,此时 i 取值为 13,而 5 仍然不能被 13 整除,所以 i 又自加 1,此时 i 取值为 14,而 5 仍然不能被 14 整除,所以 i 又自加 1,此时 i 取值为 15,由于 5 不能被 15 整除,所以 i 自加 1,此时 i 取值为 16,由于 5 不能被 16 整除,所以 i 又自加 1,此时 i 取值为 17,由于 5 不能被 17 整除,所以 i 又自加 1,此时 i 取值为 18,由于 5 不能被 18 整除,所以 i 又自加 1,此时 i 取值为 19,而 5 不能被 19 整除,所以 i 自加 1,此时 i 取值为 20,而 5 不能被 20 整除,所以 i 又自加 1,此时 i 取值为 21,由于 5 不能被 21 整除,所以 i 自加 1,此时 i 取值为 22,由于 5 不能被 22 整除,所以 i 自加 1,此时 i 取值为 23,而 5 不能被 23 整除,所以 i 自加 1,此时 i 取值为 24,由于 5 不能被 24 整除,所以 i 又自加 1,此时 i 取值为 25,由于 5 可以被 25 整除,我们记录下 5 x 2,然后将 25 除以 5 得到 1。此时 n 等于 1,因此分解完成,最终结果为 [[2, 3], [5, 2]],表示 200=2^3 x 5^2。
阅读全文