Hatena::Groupactionscript

nitoyon.dispatchEvent(null)

 | 

2010-04-18

Project Euler #46

| 01:44 | Project Euler #46 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #46 - nitoyon.dispatchEvent(null)

Christian Goldbachは全ての奇合成数は平方数の2倍と素数の和で表せると予想した.

  • 9 = 7 + 2×1^2
  • 15 = 7 + 2×2^2
  • 21 = 3 + 2×3^2
  • 25 = 7 + 2×3^2
  • 27 = 19 + 2×2^2
  • 33 = 31 + 2×1^2

後に, この予想は誤りであることが分かった.

平方数の2倍と素数の和で表せない最小の奇合成数を答えよ.

Problem 46 - PukiWiki

素数でない奇数 n を順番に確認していく。n より小さい奇数素数で引いて、2で割って、平方根とったものが整数であれば表せる数となる。つまり n より小さい全ての奇数素数で引いて、2で割って、平方根とったものが整数にならなくなる最初の n を求めればよい。

package{
import flash.display.Sprite;
import flash.text.TextField;
import flash.utils.setTimeout;

public class Problem46 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));
    private const N:int = 1000000;
    private var primes:Array;
    private var _isPrime:Object;

    public function Problem46(){
        enumPrime();
    }

    private function doit():void {
        var n:int = 1;
        setTimeout(function():void {
            for (var i:int = 0; i < 100; i++) {
                n += 2;
                if (isPrime(n)) continue;

                if (isNg(n)) {
                    t.text = n + ""; return;
                }
            }

            t.text = "checking " + n;
            setTimeout(arguments.callee, 10);
        }, 10);
    }

    private function isNg(n:int):Boolean {
        if (isPrime(n)) return false;
        for (var i:int = 1; i < primes.length; i++) {
            if (n < primes[i]) return true;
            var nn:Number = Math.sqrt((n - primes[i]) / 2);
            if (nn == int(nn)) return false;
        }
        throw new Error("overflow");
    }

    private function enumPrime():void {
        var n:int = 5;
        var isNotPrime:Array = [];
        primes = [2, 3];
        _isPrime = {2: true, 3: true};
        setTimeout(function():void {
            var c:int = 0;
            for (var j:int = 0; j < 2000; j++) {
                if (n % 2 != 0 && n % 3 != 0 && !isNotPrime[n]) {
                    primes.push(n);
                    _isPrime[n] = true;
                    for (var i:int = n * 2; i < N; i += n) {
                        isNotPrime[i] = true;
                        c++;
                    }
                }
                n += 2;
                if (c > 10000 || n >= N) break;
            }

            if (n < N) {
                t.text = "check prime " + n + "...";
                setTimeout(arguments.callee, 10);
            } else {
                doit();
            }
        }, 10);
    }

    private function isPrime(n:int):Boolean {
        if (n < N) return _isPrime[n];
        
        t.text = "overflow";
        throw new Error("overflow");
    }
}
}
 |