2

我发现了类似的问题，但这有点复杂。

我有一个很大的数 n（我实际上有更多，但现在没关系），（>40 位），我想找到 a*b*c=n 三元组。n 的素数分解完成。它没有大素数除数，但有许多小的素数除数。所有素数除数（包括多个除数）之和大于 50。

我想找到 a*b*c=n 三元组，其中 a<=b<=c。我不想要所有的三胞胎，因为它们太多了。我正在寻找特殊的。

例如：

  • ca 最小的三元组，
  • c/a 最小的三元组，
  • a、b 和 c 具有最大公约数的那个，
  • 这些条件结合起来。

如果我们知道 n=k!（阶乘），这可能会更容易解决。求解可能导致通用方法。由于 n 的大小，用蛮力计算所有这些三元组不是一种选择，所以我需要一个好的算法或一些特殊的工具来帮助我实现一个解决方案。

对不起，我的英语不好，

感谢您的回答！

4

2 回答 2

0

您可以使用简单的O(|D|^2)算法来实现它，其中是您已经拥有D的所有除数的有序列表。n

请注意，您只需要找到a,b，因为c=n/(a*b)，所以问题归结为找到所有对(a,b)，D所以a<b和n/(a*b) ∈ D。

伪代码：

result = empty_list
for (int i=0; i<D.size-1, i++) {          // O(|D|)
    for (j=i+1; j<D.size, j++) {          // O(|D|)
         a, b = D[i], D[j]
         c = n/(a*b)
         if (D.contains(c) && c>b) {      // O(1)
             result.append( (a,b,c) )
         }
    }
}                                         // O(|D|)*O(|D|)=O(|D|^2)
于 2013-03-13T13:33:37.097 回答
0

我可能有解决方案，但我今天没有时间实施它。我把它写下来，所以也许有人会同意我的观点，或者会发现我算法的弱点。

所以让我们看看第一种或第二种情况，其中 c/a 或 ca 应该是最小的。

1：在第一步中，我使用贪心算法将 n 的素因子分成 3 组。我将有一个初始的 a、b 和 c，它们彼此之间的距离不会很远。主要因素将存储在 3 个数组中：a_pf、b_pf、c_pf。

2：在下一步中，我计算 a、b 和 c 的所有可能因子，将它们存储在不同的数组中，然后对这些数组进行排序。这些将是 a_all、b_all 和 c_all。

3：我计算 q=max(a,b,c)/min(a,b,c)。（现在我们可以说a是最小的，c是最大的）

4：我在 a_all 和 c_all 中搜索此条件下的数字：c_all[i]/a_all[j] < q。当我找到它时，我在 a_pf 和 c_pf 中更改这些值的主要因子。使用这种方法，三元组中最大和最小的成员将彼此靠近。

我重复步骤 2-3-4，直到可以为止。我认为这将在有限数量的步骤后结束。

由于三元组的成员比原来的 n 小，我希望这个解决方案最多能在几分钟内给我正确的三元组。

于 2013-03-13T18:30:10.297 回答