algorithm - 将大数分解为三元组

Question

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

我有一个很大的数n(我其实还有很多，不过现在无所谓了)，(>40位)，想求a*b*c=n个三元组。 n 的质因数分解完成。它没有大素数，但有许多小素数。所有质数除数(包括倍数除数)之和大于 50。

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

例如:

• c-a 最小的三元组，
• c/a 最小的三元组，
• a,b,c 有最大公约数的那一个，
• 结合这些条件。

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

抱歉我的英语不好，

感谢您的回答!

Answer 1

您可以通过一个简单的 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)