<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，例如）

這種做法似乎有點更簡單和優化。此外，它保證你會發現第一個三角形編號。