题解 | #质数因子#

#include <stdio.h>

int main() {
    //思路：情况1，本身就是质数，输出自身即可；
    //情况2，都是质因子，按序输出所有因子即可；
    //情况3，有质因子也有合数因子，合数因子可以再拆分为质因子；
    //处理办法1：获取数据范围内的所有质数构建质数表，然后根据质数表逐层进行
    //除法筛查；处理方法2：判断当前数据是否为质数，如果不是质数则按照一定
    //方式进行逐层筛查
    long num;//存储输入的数字
    int count=0;//用来进行格式控制，确保其输出满足数字空格的格式
    scanf("%d",&num);
    for(int i=2;i<=num;i++){
        if(i*i>num){//此处的代码是为了保证不超时而做的改进
            i=num;
        } 
	  //由于之前测试的时候在2000000014用例处出现超时，是因为2000000014=2*1000000007，逐个遍历的话
	  //需要循环次数太多，而该判断的好处在于，如果说i已经遍历到sqrt（num）的层次，那么说明此时的num必然
	  //是一个素数，则省略后续线性遍历的过程直接将i的值变成num即可
	  //另外，还可以尝试做的一个小改进是，除了2之外没有偶数的素因子，所以可以把2单独判断，后续的步长取i=i+2
	  //以减少循环总次数
        while(num%i==0){
            if(count==0){
                printf("%d",i);
                count++;
            }
            else{
                printf(" %d",i);
            }
            num = num/i;
        }
    }
    printf("\n");
    
    return 0;
}