Project Euler 249

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

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    import flash.events.Event;
    // @see http://projecteuler.net/index.php?section=problems&id=249
    public class Euler249 extends Sprite {
        private var _tf : TextField;
  
        public function Euler249() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);

            var s : int = getTimer();
            tr(solve(5000));
            var g : int = getTimer();
            tr((g - s) + " ms");
        }

	    // DP. 配列seedを
	    // seed[部分集合の和]=その和を取りうる部分集合の個数%1E16
	    // として要素を昇順になめてseedをふくらませていく。
	    // 最後に部分集合の和が素数のところだけ合計すればOK.
	    // これ以上簡単にしようがない？ので時間がやたらかかる。
        private function solve(N : uint) : Number
        {
        		var base : Array = doEratosthenes(N);
        		var allsum : uint = 0;
        		for each(var p : uint in base)allsum += p;
        		tr(allsum);
        		
        		var seed : Array = new Array(allsum + 1);
        		var i : int;
        		for(i = 0;i < seed.length;i++)seed[i] = [0, 0];
        		seed[0] = [1, 0];
        		
        		var sum : uint = 0;
        		var ind : uint = 0;
        		addEventListener(Event.ENTER_FRAME, function(e:Event) : void
        		{
        			if(ind % 10 == 0)tr("ind : " + ind + "/" + base.length);
        			p = base[ind];
        			for(i = sum;i >= 0;i--){
        				seed[i + p] = N2.add(seed[i + p], seed[i]);
 //       				seed[i + p] += seed[i];
 //       				seed[i + p] -= uint(seed[i + p] / 1E16) * 1E16;
        			}
        			sum += p;
        			ind++;
        			
        			if(ind == base.length){
		        		var primes : Array = doEratosthenes(allsum);
		        		var ret : Array = [0, 0];
		        		for each(p in primes){
		        			ret = N2.add(ret, seed[p]);
//		        			ret += seed[p];
//		        			ret -= uint(ret / 1E16) * 1E16;
				    }
				    tr(ret);
				    removeEventListener(Event.ENTER_FRAME, arguments.callee);
        			}
        		});
        		
        		return 0;
        }

        private function doEratosthenes(n : int) : Array
        {
            var nn : uint = ((n / 2 - 1) >>> 5) + 1;
            var ar : Vector.<uint> = new Vector.<uint>(nn);
            var i : uint, j : uint;
            for(i = 0;i < nn - 1;i++)ar[i] = 0xffffffff;
            ar[nn - 1] = (1 << ((n / 2 - 1) & 31)) - 1;
            
            var sq : uint = (Math.sqrt(n) - 3) >>> 1;
            for(var p : uint = 0;p <= sq;p++){
                if(ar[p >>> 5] & (1 << (p & 31))){
                    var m : uint = (p << 1) + 3;
                    var m2 : uint = m << 1;
                    for(var mm : uint = m * m;mm <= n;mm += m2){
                        var ind : uint = (mm - 3) >>> 1;
                        ar[ind >>> 5] &= ~(1 << (ind & 31));
                    }
                }
            }
            
            var ret : Array = [2];
            for(i = 0;i < nn;i++){
                for(j = 0;j <= 31;j++){
                    if(ar[i] & (1 << j))ret.push((((i << 5) | j) << 1) + 3);
                }
            }
            return ret;
        }
        
        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
            _tf.scrollV = _tf.maxScrollV;
        }
    }
}

class N2{
	public static const N : Number = 1E15;	
	public static function add(a : Array, b : Array) : Array
	{
		var r0 : Number = a[0] + b[0];
		var rp : int = Math.floor(r0 / N);
		r0 -= rp * N;
		var r1 : Number = (a[1] + b[1] + rp) % 10;
		return [r0, r1];
	}
	
	public static function sub(a : Array, b : Array) : Array
	{
		var r0 : Number = a[0] - b[0];
		var rp : int = Math.floor(r0 / N);
		r0 -= rp * N;
		var r1 : Number = a[1] - b[1] + rp;
		return [r0, r1];
	}
}