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/uhbo
 */

package {
    import flash.display.Sprite;
    import flash.events.*;
    import flash.text.TextField;
    import flash.utils.getTimer;
    import com.bit101.components.*;
    // @see http://projecteuler.net/index.php?section=problems&id=
    public class Euler extends Sprite {
        private var _tf : TextField;
  
        public function Euler() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var pb : PushButton = new PushButton(this, 350, 10);
            pb.label = "stop";
            pb.width = 100;
            pb.addEventListener(MouseEvent.CLICK, function(e : MouseEvent) : void
            {
                removeEventListener(Event.ENTER_FRAME, onEnterFrame);
            });
            
            var s : int = getTimer();
            solve();
            var g : int = getTimer();
            tr((g - s) + " ms");
        }
        
        private var primes : Array;
        private var rads : Array;
        private var ret : Number;
        private var M : int = 120000;
        
        private function solve() : void
        {
            var p : int, rad : Number;
            primes = doEratosthenes(M);
            rads = enumRads(M, primes);
            
            ret = 0;
            addEventListener(Event.ENTER_FRAME, onEnterFrame);
        }
        
        private var cur : int = 2;
        private var STEP : int = 2000;
        
        private function onEnterFrame(e : Event) : void
        {
            for(var c : int = cur;c < M && c < cur + STEP;c++){
               if(rads[c] >= c / 2)continue; // c/2の場合rads(a), rads(b)はかならず3以上となるので
               if(rads[c] >= c / 6){
                   // a = 1以外に成り立たない
                   if(rads[c - 1] < c / rads[c]){
//                       t(1 + "\t" + c);
                       ret += c;
                   }
                   continue;
               }
               
               var lp : Array = [];
               var cc : int = c;
               var sqcc : int = Math.sqrt(cc);
               for each(var p : int in primes){
                   if(p > sqcc){
                       if(cc > 1){
                           lp.push(cc);
                       }
                       break;
                   }
                   if(cc % p == 0){
                       while(cc % p == 0)cc /= p;
                       lp.push(p);
                       sqcc = Math.sqrt(cc);
                   }
               }
               
               var cdr : int = c / rads[c];
               var field : Array = new Array((c >> 1) + 1);
               field[0] = true;
               for each(var g : int in lp){
                   for(var q : int = g;q <= c / 2;q += g){
                       field[q] = true;
                   }
               }
               
               for(var a : int = 1;a < c / 2;a++){
                   if(field[a])continue;
                   var rad : Number = rads[a] * rads[c - a];
                   if(rad < cdr){
//                       tr(a, c, rads[c]);
                       ret += c;
                   }
               }
            }
            if(c == M){
                removeEventListener(Event.ENTER_FRAME, onEnterFrame);
                tr("solved!");
                tr(ret);
            }
            cur += STEP;
            tr(cur, ret);
        }
        
        private function GCD(a : int, b : int) : int
        {
            while(b > 0){
                var c : int = a % b;
                a = b; b = c;
            }
            return a;
        }
        
        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");
        }
    }
}