プロジェクトオイラー12. ~ Highly divisible triangular number ~

No.12 Highly divisible triangular number

問題.

Q. 三角数 とは, 1 からの連続した自然数の和で表される数です. 例えば 7 番目の三角数は,

\begin{align*}
1+2+3+4+5+6+7 = 28
\end{align*}

で, 7 番目までの三角数の正の約数は, 以下のようになります.

1:   1

3:   1, 3

6:   1, 2, 3, 6

10: 1, 2, 5, 10

15: 1, 3, 5, 15

21: 1, 3, 7, 21

28: 1, 2, 4, 7, 14, 28

正の約数の個数が 5 個を初めて超えるのは 28 です.

では, 正の約数の個数が初めて 500 個を超える三角数は?

 

考え方とプログラム例(Python)

正の約数の個数を求める関数

num_of_divisors()

を定義します.

約数をすべて実際に数えるのではなく, 公式を使います.

自然数 が

\begin{align*}
n = p_1^{q_1}\cdot p_2^{q_2}\cdots p_N^{q_N}
\end{align*}

( は異なる素数)

と素因数分解されるとき,

約数の個数 num_of_divisors(n) は,

num_of_divisors(n) =

となることを利用します

#include<bits/stdc++.h>
using namespace std;

int num_of_divisors(int n){
  int ret = 1;
  int i = 2;
  while(n != 1){
    int num = 1;
    while(n % i == 0){
      n /= i;
      num += 1;
    }
    ret *= num;
    i += 1;
  }
  return ret;
}

int main(){
  int n = 1;
  int Tn;
  while(1){
    Tn = n * (n + 1) / 2;
    if (num_of_divisors(Tn) > 500){
      cout << Tn << endl;
      break;
    }
    n += 1;
  }
  return 0;
}