2017年03月05日

TypeScriptでProject Euler #10 「素数の和」

   このエントリーをはてなブックマークに追加 Clip to Evernote
Project Euler やっと当初の目標の10問目まできました。

問題

10以下の素数の和は 2 + 3 + 5 + 7 = 17 である.

200万以下の全ての素数の和を求めよ.

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


最初のバージョン

200万以下のすべての素数をどうやって求めるかという問題ですね。 TypeScriptでProject Euler #7 「10001番目の素数」で素数を列挙する PrimeNumberクラスを書いているので、それを使って書いてみました。


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

class Solver {
    exec(maxnum: number): number {
        let primes = PrimeNumber.enumerate();
        let sum = 0;
        for (let n of primes) {
            if (n > maxnum)
                break;
            sum += n;    
        }
        return sum;
    }
}

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

Application.run();

素数がわかれば、あとは合計するだけなのでそれほど難しくないですね。

次に書いたバージョン

もうすこし速くしたいので、エラストテネスの篩のアルゴリズムを使って、あらたに Primesクラスを書いてみました。Primesクラスのソースを示します。

export class Primes {
    private _sieve = new Array<number>();

    private _sieveSize: Number;

    public constructor(sieveSize: number) {
        this._sieveSize = sieveSize;
        this._sieve = this.sieveOut(sieveSize);
    }

    private sieveOut(maxnum: number): number[] {
        let sieve = new Array(maxnum + 1);
        for (let l = 0; l <= maxnum; l++) {
            sieve[l] = l;
        }
        sieve[1] = -1;  // -1 : 素数ではない
        let squareroot = Math.sqrt(maxnum) | 0;
        for (let i = 2; i <= squareroot; i++) {
            if (sieve[i] > 0)
                for (let n = i * 2; n <= maxnum; n += i)
                    sieve[n] = -1;
        }
        return sieve;
    }
    
    public toArray(): number[] {
        let ary: number[] = [];
        return this._sieve.map((n, ix) => n > 0 ? ix : -1).filter((n, ix) => n > 0);
    }

    public isPrime(n: number): boolean {
        return this._sieve[n] != -1;
    }
}

まだ、メソッドの先頭を小文字にするのに慣れてません(^^;; ついつい、C#のように大文字にしたくなります。

enumerateメソッドで列挙するのではなく、toArrayメソッドで配列として素数を取り出せるようにしてみました。

このPrimesクラスは、今後も使うかもしれないので、primes.ts として独立させておきます。

これを呼び出すように、Solverクラスを書き換えます。

import * as Utils from './utils';
import { Primes } from './math/primes';

class Solver {
    exec(maxnum: number): number {
        let primes = new Primes(maxnum);
        return primes.toArray().reduce((x,y) => x + y);
    }
}

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

Application.run();

実行してみると...

あれ? 最初のバージョンよりもあきらかに遅いです。

ちゃんとプロファイリングしたわけではないので、正確なところはわかってませんが、たぶん、toArrayメソッドで配列にしているところか、reduceメソッドが遅いとしが考えられません。

最終バージョン

ということで、toArrayメソッドをやめて、素数を列挙する enumerate メソッドを Primesクラスに追加します。

    public * enumerate(): IterableIterator<number> {
        for (let i = 0; i < this._sieveSize; i++) {
          if (this._sieve[i] > 0)
              yield this._sieve[i];
        }
    }

Solverクラスのexecメソッドをenumerate使うように変更します。

    exec(maxnum: number): number {
        let primes = new Primes(maxnum);
        let sum = 0;
        for (let n of primes.enumerate()) {
            if (n > maxnum)
                break;
            sum += n;    
        }
        return sum;
    }

これで、最初のバージョンよりも3倍ほど速くなりました。めでたしめでたし(^o^)...


それにしても、C#のLINQに慣れてしまうと、ループ書くのがほんとうに面倒になりますね。


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



 

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

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