质数因子

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

输入描述：输入一个整数

输出描述：按照从小到大的顺序输出它的所有质数的因子，以空格隔开。最后一个数后面也要有空格。

示例1：输入：180，输出：2 2 3 3 5

方法一：

思路分析： 首先质因子的概念为在数论里，某一正整数的质因子指能整除该数的质数。比如$66$的质因子是$33$和$22$，$6=3\ast 26\; =\; 3\; *\; 2$。$100100$有$22$个质因子：$22$和$55$。($100=2\ast 50100\; =\; 2\; *\; 50$, 且$100=5\ast 20100=5\; *\; 20$，只有$22$和$55$是质数)，因为本题题目要求按照从小到大的顺序输出它的所有质因子包括重复的数据，输出结果特别注意用空格隔开，本题可以逐个记录变量的值，设定一个指针变量$ii$，用来记录质因子，从数字2开始，只要能被输入数据整除，就将$ii$值记录，然后将i值重新定义到$22$，继续循环判断，如果不能被整除，就将i值自增，最终将$resres$输出即可。 图解：

核心代码：

#include<stdio.h>

int main(){
    int res=0;
    scanf("%d",&res);//输入
    for(int i=2;i*i<=res;){
        if(res%i==0){//能够整除说明i是质因子
            printf("%d ",i);
            res=res/i;
            i=2;//重复的不能漏掉
        }
        else
            i++;//不能整除重新判断
    }
    printf("%d ",res);
}

时间复杂度：一个嵌套循环，始终要保证i方≤res，故平均时间复杂度为$O(\sqrt{n})O(\backslash sqrt\{n\})$。

空间复杂度：不需要借助辅助数组，因此空间复杂度为$O(1)O(1)$。

方法二：

思路分析：同样，也可以采用递归的方法，如果能被整除$num\mathrm{\%}i==0num\; \backslash \%\; i\; ==\; 0$，则记录以后进入递归继续进行判断，为了减少循环的次数，对$numnum$进行开根号处理，这样会导致可能最后一个不被记录，因此还需要加一条语句，将最后一个质数输入即可。

核心代码：

num = int(input())

def division(num):
    for i in range(2,int(num**0.5+1)):#**0.5表示开根号，int表示强制转换为整数
        if num % i == 0:##可以被整除
            print(str(i), end=' ')
            num = num // i
            division(num)#递归
            break
    else:
        print(str(num), end=' ')#最后一个可能是它本身

division(num)

时间复杂度： 一个$forfor$循环，用来查找合适的$ii$值并记录，一个递归用来加载下一个$numnum$数。故平均时间复杂度为$O(n\sqrt{n})O(n\backslash sqrt\{n\})$。

空间复杂度：不需要借助辅助数组，因此空间复杂度为$O(1)O(1)$。