引き続き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);
#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秒。どちらにせよ効率の悪いアルゴリズムが原因ですね。