Hatena::Groupactionscript

nitoyon.dispatchEvent(null)

 | 

2010-04-25

Project Euler #69

| 16:38 | Project Euler #69 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #69 - nitoyon.dispatchEvent(null)

オイラーのトーティエント関数、φ(n)[時々ファイ関数とも呼ばれる]は、nと互いに素なn未満の数の数を定める。たとえば、1、2、4、5、7、そして8はみな9未満で9と互いに素であり、φ(9)=6.

n互いに素な数φ(n)n/φ(n)
2112
31,221.5
41,322
51,2,3,441.25
61,523
71,2,3,4,5,661.1666...
81,3,5,742
91,2,4,5,7,861.5
101,3,7,942.5

n ≤ 10ではn/φ(n)の最大値はn=6であることがわかる。

n ≤ 1,000,000で n/φ(n) が最大となる値を見つけよ。

Problem 69 - PukiWiki

トーティエント関数を求める処理が複雑そうで敬遠していたが、オイラーのφ関数 - Wikipedia によると、φ=n*(1-1/p_1)*(1-1/p_2)...*(1-1/p_k) で求められるとのことなので、n/φ を求めるのも簡単。

あとは素因数分解すればよいだけ。100万までの数を順番に素因数分解する処理がだいぶ重かったが、少し我慢すれば求められた。

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

public class Problem69 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 Problem69(){
        enumPrime();
    }

    private function doit():void {
        var maxValue:Number = 0;
        var max:int = 0;
        var n:int = 1;
        setTimeout(function():void {
            for (var i:int = 0; i < 1000; i++) {
                var m:int = n;
                var v:Number = 1;
                for each (var p:int in primes) {
                    if (m % p == 0) {
                        v *= (1 - 1.0 / p);
                        while (m % p == 0) {
                            m /= p;
                        }
                    }
                    if (m == 1) break;
                }
                v = 1 / v;

                if (maxValue < v) {
                    maxValue = v;
                    max = n;
                }

                if (n >= 1000000) {
                    t.text = max + "\n" + maxValue;
                    return;
                }

                n++;
            }

            t.text = "calc " + n + " min: " + max;
            setTimeout(arguments.callee, 10);
        }, 10);
    }

    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);
    }
}
}
 |