algorithm - 除数问题

Question

给定除数的数量，我们必须找到第一个三角形数。

三角形数等于自然数之和。

我采用了从 2 开始取素数并排列它们的方法，以使生成的数字与三角形数匹配。

例如，假设我们有 5 个除数。我从 2 开始取素数(2,3,5)作为N=p1^a1*p2*a2*p3^a3. 除数的数量在(a1+1)(a2+1)....这里2,3,5可以取幂和排列。然后n^2+n=2k（k是从排列得到的值）。我检查 n 值是否为整数。

除此之外，我还没有找到任何有效的算法，有没有更优化的算法？

Answer 1

您可以使用反向方法。由于第 n 个三角形数可以找到为 (n^2 + n)/2，因此您只需迭代 n 并为每个数字计算其除数。一些优化：

• (n^2+n)/2 = n(n+1)/2。n 和 n+1 没有公约数（除了 1），只有一个是偶数。因此，除数的数量或者是n/2和n+1的除数的乘积，或者是n和(n+1)/2的除数的乘积。
• 除数的数量可以通过您提到的公式找到，因此您只需要一个素数列表（例如在这里获取）

这种方法似乎更直接和最优。此外，它保证您会找到第一个三角形数。