Project Euler No.5

引き続きProject EulerをMatlab/Octaveで解いてます。

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

2520は1から10の数で割り切れる最小の数である。同様に1から20で割り切れる最小の数は何か。

単純に1から順にすべての数を1〜20の数で割りきれるかどうかチェックしています。実行すると、答えを計算するまでかなり時間がかかります。(2 x 2.66GHz Dual-Core Intel XeonのMac OS X 10.5.8で約302秒)

num = 1;
divis = 1:20;

while true
  x = 0;
  for n=1:length(divis)
    x = x+mod(num, divis(n));
  end
  if x==0
    break;
  end
  num = num+1;
end
disp(num);

同じアルゴリズムをC言語でも実装してみました。

#include <stdio.h>

int main(void) {
  long int num = 1;
  int n, x;
  
  while (1) {
    x = 0;
    for (n=1; n<=20; n++) {
      x += (num % n);
    }
    if (x == 0) {
      break;
    }
    num++;
  }
  printf("%d\n", num);
}

こっちの実行時間は約62秒。どちらにせよ効率の悪いアルゴリズムが原因ですね。