<Algorithms >除数问题

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的除数。
• 个因数可以通过你所提到的公式得到，所以你只需要素数的列表（得到它here，例如）

这种做法似乎有点更简单和优化。此外，它保证你会发现第一个三角形编号。