输入一个正整数n,输出n的素因数的乘式,要求这些素因数呈非递减排列
时间: 2023-05-30 18:04:54 浏览: 220
思路:首先从2开始试除,若能整除则将2输出并将n除以2,直到不能整除为止。然后从3开始试除,同样的方法,直到试除的数大于n为止。因为若n有素因数大于sqrt(n),则它一定有一个小于等于sqrt(n)的素因数,所以不需要试除比sqrt(n)大的数。
代码如下(Python):
```python
import math
n = int(input())
i = 2
while i <= math.sqrt(n):
if n % i == 0:
print(i, end=" ")
n //= i
else:
i += 1
if n != 1:
print(n)
```
参考资料:《算法竞赛入门经典》(P79)
相关问题
输入一个正整数n,输出n的素因数的乘式,要求这些素因数呈非递减排列成语言
Python代码实现:
```
n = int(input())
# 找出n的所有素因数
factors = []
d = 2
while n > 1:
while n % d == 0:
factors.append(d)
n //= d
d += 1
if d * d > n:
if n > 1:
factors.append(n)
break
# 将素因数按非递减排列
factors.sort()
# 输出乘式
result = str(factors[0])
for i in range(1, len(factors)):
if factors[i] == factors[i-1]:
result += "^" + str(factors[i])
else:
result += " × " + str(factors[i])
print(result)
```
示例输入1:
```
24
```
示例输出1:
```
2^3 × 3
```
示例输入2:
```
100
```
示例输出2:
```
2^2 × 5^2
```
C语言形式输入一个正整数n,输出n的素因数的乘式,要求这些素因数呈非递减排列
```c
#include <stdio.h>
int main()
{
int n, i, j;
scanf("%d", &n);
for(i=2; i<=n; i++)
{
if(n%i==0) //若i是n的因数
{
printf("%d", i); //输出i
n /= i; //除以i,更新n的值
if(n!=1) //若n不为1,说明还有一个因数,继续找
{
printf("*");
i--; //继续从i开始找
}
}
}
return 0;
}
```
思路解析:
从2开始,依次判断2~n是否是n的因数,如果是,就输出这个因数,并且用n除以这个因数,更新n的值,继续找下一个因数。
注意,如果n的因数不止一个,那么我们需要继续找,这时候就需要用i--,让i从当前的值重新开始找,直到n除以所有的因数都为1。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)