2017年02月23日

TypeScriptでProject Euler #7 「10001番目の素数」

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

問題

素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である.

10001 番目の素数を求めよ.

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

素数を列挙する

まずは、素数を列挙する関数を作成。他でも使えそうなので、別ファイル(primeNumber.ts)として独立させておきます。これは、mathフォルダに入れておきます。

とりあえず、ナイーブな実装で良しとします。

export class PrimeNumber {
    public static * enumerate(): IterableIterator<number> {
        yield 2;
        let i = 3;
        while (true) {
            if (PrimeNumber.isPrime(i))
                yield i;
            i += 2;
        }
    }

    public static isPrime(n: number): boolean {
        let r = Math.sqrt(n);
        for (let i = 3; i <= r; i += 2) {
            if (n % i === 0)
                return false;
        }
        return true;
    }
}

問題を解く

上記PrimeNumberクラスを使い、問題を解くコードを書きます。

import * as Utils from './utils';
import { PrimeNumber } from './math/primeNumber';

class Solver {
    exec(maxnum: number): number {
        let i = 0;
        for (let n of PrimeNumber.enumerate()) {
            if (++i >= maxnum)
                return n;
        }
        // ここには到達しない。
        return -1;
    }
}


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

Application.run();

10001番目を求めるループがダサいけど、LINQが標準でないので、我慢します。

自分で、IterableIterator<T> の拡張メソッドskip(n)を書こうと思ったのですが、どう書いたら良いのかわかりませんでした。TypeScriptで拡張メソッド書くには、protptypeに突っ込めばいいんだよという記事を見つけたのですが、interfaceに対してだと、どうやってやったら良いのかわかりませんでした。

まだまだ TypeScriptの知識は不足していますね。



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



 

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

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