0

我有一个小于 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);
    }
    }
}

加倍是这样的：

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

};

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

4

5 回答 5

1

您可能知道，因式分解是一个难题。您可能还知道您只需要测试素数的可分性。一个小而广为人知的提示：您只需要测试 n 的平方根。我把推理留给你。

看看埃拉托色尼的筛子。也许你在这些问题和答案中找到了暗示？那个怎么样？

如果你想让这个速度更快 - 没有这个答案的空间/时间的全部交易- 提前计算所有素数直到 500,000,000 的平方根并将它们放入一个数组中。显然，当上限增长时，这会被打破；）

于 2010-08-27T09:47:13.433 回答
0

开始研究算法。
最快的分解算法是什么？

于 2010-08-27T09:49:34.503 回答
0

预先分解最多 500,000,000 的所有整数（不管如何），并将这些因数存储在数据库或固定长度记录格式中。您的查找速度会很快，并且数据库应该适合现代 PC。

这是时间/空间权衡的一个结束，但您没有说您要优化什么。

或者，查看 GNU coreutils“因素”的算法。

于 2010-08-27T09:52:07.213 回答
0

您可以尝试 Pollard 的 rho 启发式算法，它适用于除数相对较小的复数：

波拉德氏 rho

于 2010-08-27T09:52:11.190 回答
0

如果这是一个家庭作业，我相信你应该重新阅读你的讲座材料。

无论如何，你知道你的数字是复合的而且非常小，这很好。

对于所有数字的幼稚试验划分，您最多需要 sqrt(500000000) 测试 - 对于最坏的情况，这大约是 22360 次。您显然可以跳过偶数，因为它们可以被 2 整除（先检查一下）。所以这变成了 0.01 秒的 11180 格。如果您的计算机每秒可以进行 110 万次分割，那么您可以使用简单的方法。

或者，您可以离线制作一个素数列表，最高可达 sqrt(500M)，然后尝试其中的每一个。这将进一步减少分歧。

或者，如果这些因素之间的距离不是太远，您可以尝试费马的方法。

如果这些都不起作用，您可以尝试使用 Pollard 的 rho 等。

或者，如果这不是家庭作业，请重述问题以解决限制（正如一些人所建议的，您可以预先计算因数等）。

于 2010-08-27T12:58:35.960 回答