算术基本定理(将一个正整数分解质因数),又称为正整数的唯一分解定理,即:每个大于1的自然数(且不是质数)均可分解为质数的积,而且这些质因数按小大排列之后,写法仅有一种方式(唯一的)。请编写程序对输入的
时间: 2023-04-24 11:03:16 浏览: 84
正整数进行分解质因数,并按照从小到大的顺序输出质因数。
以下是一个Python的实现:
```python
def prime_factorization(n):
factors = []
i = 2
while i * i <= n:
if n % i:
i += 1
else:
n //= i
factors.append(i)
if n > 1:
factors.append(n)
return factors
n = int(input("请输入一个正整数:"))
factors = prime_factorization(n)
print("{}的质因数分解为:{}".format(n, " × ".join(map(str, factors))))
```
这个程序中,我们定义了一个`prime_factorization`函数,它接受一个正整数`n`作为参数,返回一个列表,其中包含`n`的所有质因数。具体实现是通过一个循环,从2开始逐个检查`n`是否能被整除,如果可以,就将这个因子加入到列表中,并将`n`除以这个因子,继续检查。如果最后`n`仍然大于1,说明它本身就是一个质数,也将它加入到列表中。
在主程序中,我们首先读入一个正整数`n`,然后调用`prime_factorization`函数得到它的质因数列表。最后,我们使用`join`函数将这个列表中的元素用“ × ”连接起来,形成一个字符串,输出到屏幕上。