Hatena::Groupactionscript

nitoyon.dispatchEvent(null)

 | 

2010-03-21

Project Euler #58

| 11:26 | Project Euler #58 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #58 - nitoyon.dispatchEvent(null)

数字を渦巻き状に並べていったときの対角部分には素数がくることが多いが、確率が10%以下になるのは何重の渦巻きになったときだろうか、という問題。右下の成分は (n+1)^2 になることが自明なので、そこから n 重のときのそれぞれの対角部分の値を求めることができる。あとは素数かどうかを判定すれば OK。

ただし、1000万を超える数が素数であるかを判定しなきゃいけないので、エラトスネスの篩だけでは時間がかかりすぎる。10万までの素数を列挙しておいて、それ以降は10万以下の素数で割り切れるかで判定した(nが素数であるかを判定するには√n以下の数字で割り切れるかを調べれば十分)。

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

public class Eular extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));
    private var isPrime:Object = {};
    private var primes:Array = [];
    private const N:int = 10 * 10000;

    public function Eular() {
        t.autoSize = "left";
        enumPrime();
    }

    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 doit():void {
        var count:int = 3;
        var prime:int = 0;
        var total:int = 1;

        setTimeout(function():void {
            for (var k:int = 0; k < 100; k++) {
                var a:int = Math.pow(count - 2, 2);
                for (var i:int = 0; i < 4; i++) {
                    a += count - 1;
                    if (a > N * N) { t.text = "overflow " + count; return; }
                    else if (a < N) {
                        if (isPrime[a]) { prime++; }
                    } else {
                        var j:int;
                        for (j = 0; j < primes.length; j++) {
                            if (a % primes[j] == 0) break;
                            if (a < Math.pow(primes[j], 2)) { prime++; break; }
                        }
                    }
                    total++;
                }

                if (prime / total < 0.1) {
                    t.text = count + " (" + prime + "/" + total + ")";
                    return;
                } else {
                    t.text = (Math.floor(prime / total * 1000) / 10) + "% (" + prime + "/" + total + ")";
                    count += 2;
                }
            }
            setTimeout(arguments.callee, 10);
        }, 10);
    }
}
}
 |