题解 | #质数因子#

#include <iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;


int main() {
  int n;
  cin>>n;
  int oldn=n;
  int i=2;
  while(i<=sqrt(n) and n>1){
    if(n%i==0){
 cout<<i<<" ";
 n/=i;
    }
   
    else
     i++;
  }
  
if(oldn==n)//n没有变，输出n本身
cout<<oldn;
else//n变了，说明可以被除尽，输出最后一个因子
 cout<<n;
}
// 64 位输出请用 printf("%lld")

许多人的代码都运行超时，这里对超时原因分析如下：

1.被题目误导，把重点放到了质数上。

我本人就是这样被误导，折腾了一个小时。（无奈脸）。但是仔细想一下这个题根本不需要理会质数。

假设以如下循环

for（int i=2;i<sqrt(n);)

if(n%i==0)

{

n/=i;

cout<<i<<" ";

}else

i++}

只需要从2开始，n不断的重复除以2，直到n不能被2整除。那么n就不会被2的倍数整除，也就是不会得到为2的倍数的因子，所以得到的因子本身就是质数。不需要判断。

当i=3时同样不断用三除n，直到不能整除。

i=4时，由于4是2的倍数，所以在i=2时已经把n可以被4整除的情况给除完了。所以不会得到因子4.

以此类推，只需要不断从小到大分别除尽，就不会得到非质数的因子。

在最后只需判断n是不是质数，这里n如果没有变，那么就说明不能被整除，就是质数。

2.只需要对i<=sqrt(n)进行判断即可，不需一直判断到i==n。