2017年02月17日

TypeScriptでProject Euler #5「最小の倍数」

   このエントリーをはてなブックマークに追加 Clip to Evernote

問題

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.

では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.

   Project Euler日本語翻訳サイト から引用

考え方

配列用意して、 素数を求める際に使うエラストテネスの篩いのような感じで、素因数を求めていくやり方です。 こうすれば、かなり速く求めることができると思います。

例えば、1から10までの場合は、

1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 が最大の値です。これを
1 * 2 * 3 * 2 * 5 * 1 * 7 * 2 * 3 * 1 のようにすれば最小値が求まります。

これを nまでと一般化すれば、[0,1,2,3,4,5,6,7,8,9,10, ... n] という 配列用意して、以下の手順で配列の値を変更していきます。

  1. 4,6,8,10... 番目の値を 2番目の値(この場合2) で割った値に置き換える

  2. 6,9,12... 番目の値を 3番目の値(この場合3) で割った値に置き換える

  3. 8,12,16...番目の値を 4番目の値(すでに2で割っているので2)で割っていく。

  4. 10,15,20 ...番目の値を 5番目の値で割っていく。

  5. 以下同様

これをnまで繰り返していって、最後に、これらの値(0番目は除きく)をすべて掛けあわせれば答えを求めることができます。

TypeScriptのコード

まず、連番を求める関数 makeSeq を定義します。これれは、以前作成した utils.tsファイルに追加することにします。

    export function makeSeq(begin: number, end: number): Array<number> {
        let ary = new Array(end - begin + 1);
        let i = 0;
        for (let n = begin; n <= end; n++)
            ary[i++] = n
        return ary;
    }

これを使った問題を解くコードを以下に示します。

import * as Utils from './utils';
import Stopwatch = Utils.Stopwatch;

class Solver {
    exec(n: number): number {
        let nums = Utils.makeSeq(0, n);
        for (var j = 2; j < nums.length/2; j++) {
            let d = nums[j];
            if (d === 1)
                continue;
            for (let k = j + j; k <= n; k += j) {
                nums[k] = nums[k] / d;
            }
        }
        let r = 1;
        nums.slice(2).forEach(x => r *= x);
        return r;
    }
}

class Application {
    static run(): void {
        let sw = Stopwatch.startNew();
        try {
            let p = new Solver();
            let n = p.exec(20);
            console.log(n);
        } finally {
            sw.stop();
            console.log(sw.toString());
        }
    }
}

Application.run();

僕のマシンだと 20ミリ秒ほどで求めることができました。

おまけ

ここまで書いて気が付いたのですが、

let r = 1;
nums.slice(2).forEach(x => r *= x);
return r;

上の3行は、以下の行に置き換え可能ですね。

return nums.slice(2).reduce((x, y) => x * y);

reduceは、LINQの Aggregate と同じような関数ですね。

slice や reduceが IterableIterator<T> に使えないのは残念だなー。外部ライブラリ探せばありそうだけど、TypeScriptの言語機能を知るのが目的なので、これ以降も初めの方針通り、外部ライブラリは使わないでいこうと思います。


※Stopwatchクラスについては、「TypeScriptでProject Euler #0」 を見てください。



 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52485095