<算法>除数问题

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的约数的乘积。
• 除数的个数可以通过您提到的公式找到，因此您只需要一个素数列表（在此处获取< /a>，例如）

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