Project Euler 243

/**
 * Copyright uwi ( http://wonderfl.net/user/uwi )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/xfg2
 */

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=243
    public class Euler243 extends Sprite {
        private var _tf : TextField;
  
        public function Euler243() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            t(solve(10000000));
            t(solve23());
            var g : int = getTimer();
            t((g - s) + " ms");
        }

        // これから、2*・・・*23と2*・・・*29の間にあることがわかる。
        // が、d=2*・・・*23のとき φ(d)/d<15499/94744<φ(d)/(d-1)
        // となっているので、2*・・*23に1~(29-1)のどれかをかけたものが求めるdになりそう。
        private function solve(M : int) : Number
        {
            var primes : Array = doEratosthenes(100);
            var r : Number = 1.0;
            var d : Number = 1;
            for each(var p : int in primes){
                r = r * (p - 1) / p;
                d *= p;
                t(p + "\t" + (r * d / (d - 1)) + "\t" + r + "\t" + 15499/94744);
                if((r * d / (d - 1)) < 15499/94744){
                    return d;
                }
            }
            return 0;
        }
        
        private function solve23() : int
        {
            var n : int = 2*3*5*7*11*13*17*19*23;
            var d : int = 1*2*4*6*10*12*16*18*22;
            
            for(var i : int = 1;i <= 28;i++){
                var r : Number = d * i / (n * i - 1);
                t(i + "\t" + (n * i) + "\t" + r + "\t" + 15499/94744);
                if(r < 15499/94744){
                    return n * i;
                }
            }
            return 0;
        }

/*
        // 愚直にやったらしぬ
        private function solve(M : int) : int
        {
            var primes : Array = doEratosthenes(M);
            var totients : Array = enumTotient(M, primes);
            for(var d : int = 2;d <= M;d++){
                var r : Number = totients[d] / (d - 1);
                if(r < 15499/94744){
                    return d;
                }
            }
            return -1;
        }
        */
        
        private function enumTotient(n : int, primes : Array) : Array
        {
            var ret : Array = new Array(n + 1);
            var i : int;
            for(i = 0;i <= n;i++)ret[i] = i;
            
            for each(var p : int in primes){
                for(i = p;i <= n;i += p){
                    ret[i] = ret[i] / p * (p - 1);
                }
            }
            
            return ret;
        }

        private static function doEratosthenes(n : int) : Array
        {
            var ar : Vector.<uint> = new Vector.<uint>(n / 2 - 1);
            var i : int;
            for(i = 0;i < ar.length;i++)ar[i] = 1;
            
            var sq : int = (Math.sqrt(n) - 3) >> 1;
            for(var p : int = 0;p <= sq;p++){
                if(ar[p] == 1){
                    var m : int = (p << 1) + 3;
                    var m2 : int = m << 1;
                    for(var mm : int = m * m;mm <= n;mm += m2){
                        ar[(mm - 3) >> 1] = 0;
                    }
                }
            }
            var ret : Array = [2];
            for(i = 0;i < ar.length;i++){
                if(ar[i] == 1)ret.push((i << 1) + 3);
            }
            return ret;
        }
        
        private function t(o : *) : void
	{
            _tf.appendText("" + o + "\n");
	}
    }
}