我也发现了类似的问题,但这有点复杂。
我有一个很大的数字n(实际上我有更多,但现在不重要了),(大于40位数),我想找到a*b*c=n个三元组n的主因子分解完成了它没有大素因子,但有许多小素因子所有素因子(包括多个因子)之和大于50。
我想找个a*b*c=n三胞胎,其中a例如:
c-a最小的三元组,
C/A最小的三元组,
其中A、B和C具有最大公因数,
这些条件结合在一起。
如果我们知道n=k,这个问题就更容易解决了!(阶乘)。解决问题可以得到一个通用的方法。
由于n的大小,用蛮力计算所有这些三元组不是一个选项,因此我需要一个好的算法或一些特殊工具来帮助我实现这个解决方案。
对不起我的英语不好,
谢谢你的回答!

最佳答案

你可以用一个简单的,O(|D|^2)算法来实现它,其中D是一个所有除以n的数字的有序列表,你已经有了这个列表。
注意,您只需要找到a,b,因为c=n/(a*b),所以问题归结为在(a,b)中找到所有对D,这样a<bn/(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)

10-06 05:03