Project Euler No.12

Project Euler続き。12問目。

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

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

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

約数の数が500よりも大きくなる三角数はのうち最も小さい数はいくつか？

下記のようなプログラムをMatlabで作って走らせたら、15分たっても終わりません。

n = 1;
while true
  x = sum(1:n);
  c = 0;
  for m = 1:x
    if mod(x, m)==0
      c = c+1;
    end
  end
  if c > 500
    disp(x);
    break;
  end
  n = n+1;
end

どうもおかしいということで、C言語で組み直したのが下のコード。

#include <stdio.h>

int main(int argc, char *argv[]) {
  int n = 1;
  int i, c, m;
  long int x;
  while (1) {
    x = 0;
    for (i=1; i<=n; i++) {
      x = x+i;
    }
    c = 0;
    for (m=1; m<=x; m++) {
      if (x%m==0) {
	c++;
      }
    }
    if (n % 50 == 0) {
      printf("%d\n", n);
    }
    if (c > 500) {
      printf("\n%ld\n", x);
      break;
    }
    n++;
  }
  return 0;
}

実行してみたらこちらも10分待っても20分待っても終わりません。しょうがないので放置しておいたら実行開始後88分（2.53GHz Intel Core 2 Duo）で正しい答えが計算できてました。

Project Eulerの問題は1分以内に計算ができるものが多いとのことなので、この問題に関しては要復習（復讐?）です。