利用栈的算法,质因数分解逆序输出
时间: 2023-05-25 22:05:33 浏览: 208
实现质因数分解的程序,输出这个数的质因数的连乘形式分解质因数.zip
算法步骤如下:
1. 定义一个栈,命名为 `stack` ,用于存储质因数。
2. 输入一个整数 `n` ,作为需要分解质因数的数。
3. 定义一个变量 `i` ,初始值为 2。
4. 当 `n` 大于等于 `i` 时,执行以下操作:
1. 当 `n` 能够整除 `i` 时,将 `i` 压入栈 `stack` 中,同时 `n` 除以 `i`。
2. 当 `n` 不能整除 `i` 时,将 `i` 加 1,继续循环。
5. 当 `n` 小于 `i` 时,说明 `n` 已经被分解质因数完毕。此时,从栈 `stack` 中依次取出质因数,逆序输出。
代码实现如下:
```python
def prime_factorization(n):
stack = []
i = 2
while n >= i:
if n % i == 0:
stack.append(i)
n //= i
else:
i += 1
while stack:
print(stack.pop(), end=' ')
# 测试
prime_factorization(60) # 输出 5 3 2 2
```
阅读全文