Project Euler 278

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

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=278
    public class Euler278 extends Sprite {
        private var _tf : TextField;
  
        public function Euler278() {
            _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");
        }
		
		// 2次元の場合、ax+by, a,bは互いに素でx,yが動くとすると、
		// ax+by=d(dは整数)の解は、
		// 直線ax+by=d上のx>=0, y>=0にある格子点となる。
		// よって、格子点解をぎりぎりとらなければいいのだから、
		// 格子点解が(-1, a-1), (b-1, -1)のとき(d=ab-a-b)解。
		// 
		// 3次元の場合もやはり、平面ax+by+cz=d上のx>=0,y>=0,z>=0にある格子点が解となる。
		// 今回は、a=pq, b=pr, c=qrなので、格子点解の間の単位ベクトルは
		// (r,-q,0), (r,0,-p), (0,q,-p)の3通り。
		// これらを考慮して一番ぎりぎりなのは
		// 平面が(-1,q-1,p-1)を通るときなので、
		// d=pq(-1)+pr(q-1)+qr(p-1)=2pqr-pq-qr-rp
		// が答え。
        private function solve(N : int) : Array
        {
        		var primes : Array = sieveEratosthenes(N);
        		var ret : Array = [0, 0];
        		for(var i : uint = 0;i < primes.length;i++){
				var p : uint = primes[i];
				var sum : Number = 0;
				for(var j : uint = i + 1;j < primes.length;j++){
					var q : uint = primes[j];
        				for(var k : uint = j + 1;k < primes.length;k++){
        					var r : uint = primes[k];
        					sum += 2*p*q*r-p*q-p*r-q*r;
        				}
        			}
        			N2.inc(ret, sum);
        		}
        		return ret;
        }

        private function sieveEratosthenes(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;
		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];
	}
	
	public static function inc(a : Array, b : Number) : Array
	{
		var r0 : Number = a[0] + b;
		var rp : int = Math.floor(r0 / N);
		r0 -= rp * N;
		var r1 : Number = a[1] + rp;
		
		a[0] = r0;
		a[1] = r1;
		return a;
	}
}