Project Euler 234

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

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

        // 該当する整数は、隣り合う素数をp,q(p<q)とすると、
        // p^2とq^2の間にあるp^2+up, q^2-vq (u,vは自然数)で表される。
        // チェビシェフの定理より、上記の整数のうちダブルカウントされるのはpqのみなので、
        // p^2,q^2の間にある条件をみたす整数の和は
        // P:=[(q^2-p^2)/p], Q:=[(q^2-p^2)/q]として
        //   sum_u(p^2+up)+sum_v(q^2-vq)-2pq
        // = p(p+1)P + pP(P+1)/2 + q(q-1)Q - qQ(Q+1)/2 - 2pq
        // 問題文の上限付近のQ等を少しいじって、√上限以下のすべてのpについて合計すればOK.
        private function solve(m : Number) : MPI
        {
            var sqm : Number = Math.sqrt(m);
            
            var primes : Array = doEratosthenes(sqm + 200);
            var i : int;
            var sum : MPI = new MPI(0);
            for(i = 0;i < primes.length;i++){
                if(primes[i] > sqm)break;
                var ctmap : Object = {};
                var cur : int = primes[i];
                var nex : int = primes[i + 1];
                
                var sup : Number = nex * nex;
                if(sup > m){
                    sup -= Math.floor((sup - m) / nex) * nex;
                    t("sup : " + sup);
                }
                var curn : int = Math.floor((Math.min(sup, m) - cur * cur) / cur);
                var nexn : int = Math.floor((sup - cur * cur) / nex);
//                t(cur + "\t" + nex + "\t" + curn + "\t" + nexn);
                sum.add(new MPI((cur * cur + cur) * curn + cur * curn * (curn - 1) / 2));
                sum.add(new MPI((sup - nex) * nexn - nex * nexn * (nexn - 1) / 2));
                if(cur * nex <= m)sum.sub(new MPI(2 * cur * nex));
            }
            return sum;
        }
        
        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 t(o : *) : void
	{
            _tf.appendText("" + o + "\n");
	}
    }
}


class MPI
{
    public var d : Vector.<int>;
    
    public function MPI(v : Number = 0)
    {
        if(v == 0){
            d = Vector.<int>([0]);
        }else{
            d = Vector.<int>([]);
            for(var i : Number = v;i != 0;i = Math.floor(i / 10))d.push(i % 10);
        }
    }
    
    public function carry() : void
    {
        for(var i : int = 0;i < d.length;i++){
            if(d[i] < 0){
                var cr : int = int((-d[i] - 1) / 10) + 1;
                d[i + 1] -= cr;
                d[i] += cr * 10;
            }else{
                var c : uint = d[i] / 10;
                if(c > 0){
                    if(i == d.length - 1){
                        d.push(0);
                    }
                    d[i + 1] += c;
                }
                d[i] %= 10;
            }
        }
    }
    
    public function add(n : MPI) : MPI
    {
        var i : int;
        for(i = 0;i < Math.min(d.length, n.d.length);i++){
            d[i] += n.d[i];
        }
        for(i = d.length;i < n.d.length;i++){
            d.push(n.d[i]);
        }
        carry();
        return this;
    }
    
    public function sub(n : MPI) : MPI
    {
        var i : int;
        for(i = 0;i < Math.min(d.length, n.d.length);i++){
            d[i] -= n.d[i];
        }
        for(i = d.length;i < n.d.length;i++){
            d.push(-n.d[i]);
        }
        carry();
        shave();
        return this;
    }
    
    public function mul(n : MPI) : MPI
    {
        var ret : Vector.<int> = new Vector.<int>(d.length + n.d.length);
        var i : int, j : int;
        for(i = 0;i < ret.length;i++)ret[i] = 0;
        for(i = 0;i < d.length;i++){
            for(j = 0;j < n.d.length;j++){
                ret[i + j] += d[i] * n.d[j];
            }
        }
        d = ret;
        carry();
        shave();
        return this;
    }
    
    public function shave() : void
    {
        for(var i : int = d.length - 1;i >= 1;i--){
            if(d[i] > 0)break;
            d.pop();
        }
    }
    
    public function toString() : String
    {
        var ret : String = "";
        for(var i : int = d.length - 1;i >= 0;i--){
            ret += d[i].toString();
        }
        return ret;
    } 
}