Project Euler 146

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

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=146
    public class Euler146 extends Sprite {
        private var _tf : TextField;
  
        public function Euler146() {
            _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);
            });
            
            _s = getTimer();
            solve();
            tr((getTimer() - _s) + " ms");
        }
        
        private var _s : int;
		private var _primes : Array;
        
        private function solve() : void
        {
        		_primes = doEratosthenes(M);
        	
            var pconds : Array = [1, 3, 7, 9, 13, 27];
            var failfield : Array = new Array(N);
            var i : int, j : int;
            
            // 素因数2,3,5,7,11,13,17について
            // 各n^2+cがすべて割り切れてしまうかどうかを格納する。
            var mul : int = M;
            var mul2 : Number = 1;
            for each(var p : int in [2, 3, 5, 7, 11, 13, 17]){
                var f : Array = new Array(p);
                var ct : int = 0;
                for(i = 0;i < p;i++){
                    var v : int = (i * i) % p;
                    f[i] = true;
                    for each(var c : int in pconds){
                        if((v + c) % p == 0){
                            f[i] = false;
                            break;
                        }
                    }
                    ct += f[i] ? 1 : 0;
                }
                for(j = 0;j < p;j++){
                    if(f[j])continue;
                    for(i = j;i < N;i+=p){
                        failfield[i] = true;
                    }
                }
                
                mul = mul * ct / p;
                mul2 *= p;
                tr(p, ct, mul, mul2);
            }
            
            oks = [];
            for(i = 0;i < N;i++){
                if(!failfield[i])oks.push(i);
            }
            addEventListener(Event.ENTER_FRAME, onEnterFrame);
        } 
            
        private var oks : Array;
        private var M : int = 150000000;
        private var N : int = 2*3*5*7*11*13*17;
        private var STEP : int = 5 * N;
        private var cur : int = 0;
        private var sum : Number = 0;
        private var checker : Array = [
        	0, 1, 0, 1, 0, 0, 0, 1, 0, 1,
        	0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
        	0, 0, 0, 0, 0, 0, 0, 1
        	];
        	private var era : Array = new Array(28);

        private function onEnterFrame(e : Event) : void
        {
            for(var i : int = cur;i <= M && i < cur + STEP;i += N){
                for each(var v : int in oks){
                    var n : int = i + v;
                    if(i + v > M)break;
                    for(var j : uint = 0;j < 28;j++)era[j] = 1;
                    
                    // 2段階エラトステネス
              		var f : Boolean = false;
                    for each(var p : uint in _primes){
                    		if(p >= n)break;
                    		for(var q : int = -(((n % p) * (n % p)) % p) + p;q < 28;q += p){
                    			era[q] = 0;
                    			if(q == 1 || q == 3 || q == 7 || q == 9 || q == 13 || q == 27)f = true;
                    		}
                    		if(f)break;
                    }
                    if(f)continue;
                    
                    for(j = 1;j < 28;j++){
	                    	if(era[j] != checker[j])break;
                    }
                    
                    if(j == 28){
                        tr("hit : " + n);
                        sum += n;
                    }
                }
            }
            cur += STEP;
            if(cur > M){
                tr(sum+10);
                removeEventListener(Event.ENTER_FRAME, onEnterFrame);
            }
            tr(cur, sum, (getTimer() - _s) + " ms");
        }

        private static function doEratosthenes(n : uint) : 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");
			_tf.scrollV = _tf.maxScrollV;
        }
    }
}