质数分解是一个算法中最最基本的一个问题,比如,在整数因子分解问题中就有用到。我们希望其时间复杂度应该越小越好。比较快速的方法就是,在做质数分解的时候,通常我们只需要遍历到sqrt(n)即可。这样时间复杂度就是O(n^0.5),速度还是相当可观的!!在这里给出一种比较通俗易懂的实现给大家参考:

vector<int>getPrime(int n)
{
  vector<int>res;
  int stopLoop=sqrt(n)+1.1;
  for(int i=2;i<stopLoop;i++)
  {
    if ((n%i)==0)
    {
      res.push_back(i);
      n/=i;
      i--;
    }
  }
  if(n>1)
  {
    res.push_back(n);
  }
  return res;
}