求一个正整数的各个质因数。例如:输入90,打印出90=2*3*3*5。
时间: 2023-12-30 09:06:57 浏览: 99
以下为Python代码实现:
```python
def primeFactors(n):
factors = []
# 先将所有的2除尽
while n % 2 == 0:
factors.append(2)
n //= 2
# 从3开始,每次增加2,只要n不为1,就继续尝试除
i = 3
while i <= n:
if n % i == 0:
factors.append(i)
n //= i
else:
i += 2
# 格式化输出
print(f"{n}=", end="")
for i in range(len(factors)):
if i != len(factors) - 1:
print(f"{factors[i]}*", end="")
else:
print(f"{factors[i]}")
# 测试
primeFactors(90) # 输出:90=2*3*3*5
```
思路解析:
首先,我们需要找到一个正整数n的质因数。我们可以从小到大枚举所有的正整数,判断它是否是n的因数,如果是,就将它加入到因数列表中,并将n除以它,继续尝试除下一个数,直到n不能再被除尽为止。
但是,这种方法的时间复杂度为O(n),当n非常大时,效率非常低。因此,我们需要优化一下算法。
我们发现,如果一个数n是合数,那么它的最小质因数一定小于等于$\sqrt{n}$。因此,我们只需要从2开始,每次增加1(或者增加2,因为偶数不可能为质数),只要n不为1,就继续尝试除。
当尝试除以一个数i时,如果n能够整除i,就将i加入到因数列表中,并将n除以i,继续尝试除。如果n不能整除i,就尝试除下一个数。
最后,我们只需要将输出格式化一下即可。
阅读全文