Project Euler 193

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

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

        private var _primes : Array;
        
        // 2^50未満で平方数を含む可能性のあるとき、
        // 平方される数は最大でも2^25.
        // 2^25までの素数を列挙し、
        // それらを最大1個ずつ使った2^25以下の合成数Aをすべて構成し、
        // (-1)^(使われた素数の個数-1) * [2^50 / A^2]を足し合わせる。
        private function solve(N : int) : Number
        {
            _primes = doEratosthenes(N);
            tr(_primes.length);
            return dfs(0, N, 1);
        }
        
        private function dfs(p : int, left : int, mul : Number) : Number
        {
//            tr(p, mul);
            var i : int;
            var ret : Number = Math.floor(left * left / (mul * mul));
            for(i = p;i < _primes.length && left >= mul * _primes[i];i++){
                ret -= dfs(i + 1, left, mul * _primes[i]);
            }
            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");
        }
	}
}