题意分析:本体旨在输出一个整数的所有质因数,有以下几个需要知道
- 质数:只有两个因数,1和它本身
- 因数:a可以整除b,则a就是b的因数,如2是4的因数
- 质因数:一个数即使质数又是另一个数的因数,则称为质因数
注意事项:
求解质因数时需要 这个数 本身是 质数 和 合数
- 对于质数,显然它的质因数 就是它本身 (1既不是质数也不是合数)
- 对于合数,求解质因数的过程就是 分解质因数,可以使用短除法。短除法即从最小的质数除起,一直除到结果为质数为止
根据短除法,最小的质数是2,如果可以整除,就是除数输出,把商赋值给n,直到这个质数无法整除退出。
不用担心会出现后面发现可以整除4的情况,因为可以整除4,一定可以被2整除,所以实际可以整除的都是质数。
n不断赋值循环中,最后剩下的是也必然是质数,大于2,因为我们一开始整除的2,不可能最后剩下的是2,也可能一开始输入的就是质数,因此都需要将最后的n输出
import sys
from math import sqrt
n = int(input())
# 对于一个合数,他的最大因数 一定小于或者等于它的平方根
for i in range(2,int(sqrt(n))+1):
# 只要还可以整除,就一直循环除
while n%i == 0:
print(i,end=' ')
n=n//i
# 如果最后n 还大于2,说明n是一个质数直接输出
if n>2:
print(n)

京公网安备 11010502036488号