c++ - 因数分解

Question

我有一个小于 500,000,000 的数字，我想以一种有效的方式对它进行因式分解。你建议什么算法？注意:我有 0.01 秒的时间限制!

我刚刚写了这段 C++ 代码，但它实在是太糟糕了!

void factorize(int x,vector<doubly> &factors)
{
  for(int i=2;i<=x;i++)
    {
      if(x%i==0)
    {
      doubly a;
      a.number=i;
      a.power=0;
      while(x%i==0)
        {
          a.power++;
          x/=i;
        }
      factors.push_back(a);
    }
    }
}

doubly 是这样的:

struct doubly
{
  int number;
  int power;
//and some functions!!

};

还有一点:我知道 n 不是素数

Answer 1

您可能知道，因式分解是一个难题。您可能还知道，您只需要测试质数的整除性。一个小但众所周知的提示:您只需要测试到 n 的平方根。我把推理留给你。

看看埃拉托色尼的筛法。也许您会在 these questions and answers 中找到提示？ that one怎么样？

如果你想让它变得更快——而不用 this answer 的空间/时间进行完全交易- 预先计算出所有不超过 500,000,000 平方根的素数，并将它们放入一个数组中。显然，当上限增长时，这就被打破了；)