[开发测试]HJ7 质数因子

描述

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

最后一个数后面也要有空格

输入描述：

输入一个long型整数

输出描述：

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

示例1

输入：

180

输出：

2 2 3 3 5

示例2

输入：

2000000014

输出：

2 1000000007

?AC代码

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;
 
int main(){
    LL num;
    cin>>num;
    bool ok = false;
    for(LL i=2;i<=sqrt(num);i++){
        while(num%i == 0){
            cout<<i<<' ';
            num /= i;
        }
        if(num == 1) return 0;
    }
    if(!ok) cout<<num<<' ';
     
    return 0;
}

思路

从2开始除，直到除不尽为止，那么剩下的数绝不能再除尽2的倍数...

最大的一组测试用例是2000000014，那么在2到 sqrt(2000000014) 之间如果都没有找到能除尽的数，那么就表明剩下的这个数本身就是质数。这也是本题最大的优化。