HJ6 质数因子【☆☆☆☆☆】

描述

功能:输入一个正整数，按照从小到大的顺序输出它的所有质因子（重复的也要列举）（如180的质因子为2 2 3 3 5 ）

数据范围： $$ 1 ≤ n ≤ 2 *10^9+14 $$

输入描述：

输入一个整数

输出描述：

按照从小到大的顺序输出它的所有质数的因子，以空格隔开。

示例

输入：

180

输出：

2 2 3 3 5

代码

import math
m = int(input())
 # 一个数可以被它所有的质因子表示
 # 这里仅考虑不大于根号下n的因子,如果暴力从2到自身，都会导致超时，太坑
 # 因为当n被所有不大于根号下n的【质】因子整除后，要么余1，要么余2，要么会剩下一个且仅会剩下一个大于等于根号下n小于等于n的质数（不可能出现两个不相等且同时大于根号下n的质因子a和b，这会导致a*b>n）
for i in range(2, int(m/2) + 1):      
    while int(m) % i == 0:
         # 第一个能被整除的一定是最小的质数因子（如果是合数，一定有2<=x<i的质因子x）
        # 后续能被整除的也一定是质数，若是合数，则合数的质因子肯定出现在之前，不成立
        print(i, end=' ')
        m = m // i

if m >=2:    # 大于等于2，意味着上边循环没有进入或者剩余大于根号值的数，m本身就属于质因数，输出即可
    print(m)

知识点

• Math函数