求质数因子

题目描述
功能:输入一个正整数，按照从小到大的顺序输出它的所有质因子（如180的质因子为2 2 3 3 5 ）
最后一个数后面也要有空格。
输入描述:输入一个long型整数
输出描述:按照从小到大的顺序输出它的所有质数的因子，以空格隔开。最后一个数后面也要有空格。
示例1
输入：180
输出：2 2 3 3 5

/*输入一个正整数，按照从小到大的顺序输出它的所有质因子
（如180的质因子为2 2 3 3 5 ）
最后一个数后面也要有空格。
*/
#include<iostream>
using namespace std;

void  getPrimeFactor(long n)
{
    /*要求n的质因子，只用遍历2~（n-1）之间的每一个整数i，
    如果i能被n整除，则i是n的因子；
    优化：如果i是n的质因子，则n必存在另一个因子j>sqrt(n)，
    例如：16=2*8,16=4*4，2和8分别小于大于4;因此如果在2~sqrt(n)
    之间没有因子，那么在sqrt(n)~n之间肯定不会有因子。
    所以只用遍历2~sqrt(n)之间的整数就可以了。
    通过n/=i，剔除已经求出的质因子，不断减小n，缩小循环次数
    */
    for(int i=2;i*i<=n;++i){ //1不是质数
        if(n%i==0){
            cout<<i<<" ";
            n/=i;  //剔除已经求出的质因子，更新n的值
            while(n%i==0){ //判断是否有多个值为i的质因子
                cout<<i<<" ";
                n/=i;
            }
        }
    }
    if(n>1) cout<<n<<" "; //判断最后剩下的n是否是质数
}

int main(int argc,char **argv)
{
    long n;
    cin>>n;
    getPrimeFactor(n);
    return 0;
}