Project Euler 273

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

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

        private function solve() : Number
        {
            // 150以下の4k+1型の素数を集める。
            var primes : Array = doEratosthenes(150);
            var validPrimes : Array = [];
            for each(var p : uint in primes){
                if(p % 4 == 1){
                    validPrimes.push(p);
                }
            }
            tr(validPrimes);
            
            var lim : uint = 1 << _seeds.length;
            var i : uint, j : uint, k : uint;
            
            // 素数について2平方を求める。これはただ1通りだけ存在する。
            var seeds : Array = [];
            for(i = 0;i < _seeds.length;i++){
                for(var a : uint = 1;a * a * 2 < _seeds[i];a++){
                   var b2 : uint = _seeds[i] - a * a;
                   var sqb2 : Number = Math.sqrt(b2);
                   if(int(sqb2) == sqb2){
                      break;
                   } 
                }
                seeds[i] = [a, sqb2];
                tr(_seeds[i], seeds[i]);
            }
            
            // 素数の使用の可否によりNを列挙し、
            // 2平方をブラーマグプタの二平方恒等式を使ってがんがん生成していく。
            // 2^(使っている素数の個数) 個の2平方ができるので、キャッシュすると死ぬ。
            // その都度つくる。
            var su : Number = 0;
            var sl : Number = 0;
            for(i = 1;i < lim;i++){
                var used : Array = [];
                for(j = i, k = 0;j > 0;j >>>= 1, k++){
                    if((j & 1) == 1)used.push(k);
                }
                var r : Array = seeds[used[0]];
                for(j = 1;j < used.length;j++){
                    var rk : Array = seeds[used[j]];
                    var o : Array = [];
                    for(k = 0;k < r.length;k += 2){
                        var aa1 : int = r[k] * rk[0] - r[k+1] * rk[1];
                        var aa2 : int = r[k] * rk[1] - r[k+1] * rk[0];
                        o.push(
                            aa1 > 0 ? aa1 : -aa1,
                            r[k] * rk[1] + r[k+1] * rk[0],
                            aa2 > 0 ? aa2 : -aa2,
                            r[k] * rk[0] + r[k+1] * rk[1]
                        );
                    }
                    r = o;
                } 
                
                for(k = 0;k < r.length;k += 2){
                    sl += r[k] > r[k+1] ? r[k+1] : r[k];
                    if(sl > 100000000){
                        su += Math.floor(sl / 100000000);
                        sl %= 100000000;
                    }
                }
            }
            
            tr(su, sl);
            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;
        }
    }
}