2

約数が与えられると、最初の三角形の数を見つける必要があります。

三角形数は自然数の和と同じです。

私は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 値が整数であることを確認します。

これ以外に効率的なアルゴリズムは見つかりませんでした。より最適なアルゴリズムはありますか?

4

1 に答える 1

1

逆のアプローチを使用できます。n 番目の三角形の数は (n^2 + n)/2 として見つけることができるため、n を繰り返し、各数についてその除数を数えることができます。いくつかの最適化:

  • (n^2+n)/2 = n(n+1)/2. n と n+1 には (1 を除いて) 公約数はなく、そのうちの 1 つだけが偶数です。したがって、除数の数は、n/2 と n+1 の除数の乗算、または n と (n+1)/2 の除数の乗算のいずれかになります。
  • 約数はあなたが言及した式で見つけることができるため、素数のリストのみが必要です（たとえば、ここで入手してください）

このアプローチは、もう少し簡単で最適なようです。さらに、最初の三角形の数を見つけることが保証されます。

于 2011-05-17T15:12:01.110 に答える