forked from: Project Euler 127

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

// forked from uwi's Project Euler 127
package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=127
    // 違うアプローチで（といってもほとんど同じだけど）15秒制限内で終わるようにしたバージョン
    public class Euler127 extends Sprite {
        private var _tf : TextField;
  
        public function Euler127() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            tr(solve(120000));
            var g : int = getTimer();
            tr((g - s) + " ms");
        }
        
        private function solve(M : int) : int
        {
            var primes : Array = doEratosthenes(M); // 素数列挙
            var factors : Array = enumFactors(M, primes); // 素因数列挙
            var rad : Array = enumRads(M, primes); // rad列挙
            var ct : int = 0;
            var ret : int = 0;
            var a : int, b : int, f : int;
            for(var c : int = 1;c < M;c++){
                var mul : int = c / rad[c];
                // mul=1はどのa,b,cも満たさないので不適
                // mul=2はa=1,b=1,c=2以外ありえないので不適
                if(mul >= 3){
                    var fs : Array = [];
                    for(var i : int = 0;;i++){
                        if(!factors[c][primes[i]]){
                            fs.push(primes[i]);
                            if(fs.length == 2)break;
                        }
                    }
                    
                    // a = 1, b = c - 1のパターン
                    b = c - 1;
                    if(mul > rad[b]){
                        ret += c;
                        ct++;
//                        tr(1, b, c);
                    }
                    
                    // 上以外のパターンは、cの素因数以外の2つ以上の素因数で
                    // rad[a]rad[b]が構成されるので、c/rad[c]はそれより大きくなければならない。
                    if(mul > fs[0] * fs[1]){
                        // aを構成する。(a,c)=1であればよい。
                        var modlist : Array = new Array(rad[c]);
                        for each(f in factors[c]){
                            for(i = 0;i < rad[c];i += f){
                                modlist[i] = 1;
                            }
                        }
                        var mods : Array = [];
                        for(i = 0;i < rad[c];i++){
                            if(!modlist[i])mods.push(i);
                        }
                        
                        for(var base : int = 0;base < c / 2;base += rad[c]){
                            for each(f in mods){
                                a = base + f;
                                if(a >= c / 2 || a < 2)continue;
                             
                            if(mul > rad[a] * rad[c - a]){
                                ct++;
//                                tr(a, c - a, c);
                                ret += c;
                            }}
                        }
                    }
                    
                }
            }
            tr(ct, ret);
            return ret;
        }
        
        private function enumFactors(n : int, primes : Array) : Array
        {
            var ret : Array = new Array(n + 1);
            var i : int;
            for(i = 0;i <= n;i++)ret[i] = {};
            for each(var p : int in primes){
                for(var b : int = p;b <= n;b += p){
                    ret[b][p] = p;
                }
            }
            return ret;
        }
        
        private function enumRads(n : int, primes : Array) : Array
        {
            var ret : Array = new Array(n + 1);
            var i : int;
            for(i = 0;i <= n;i++)ret[i] = 1;
            
            for each(var p : int in primes){
                for(var b : int = p;b <= n;b+=p){
                    ret[b] *= p;
                }
            }
            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 tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
        }
    }
}