Project Euler 196

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

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=
    public class Euler extends Sprite {
        private var _tf : TextField;
  
        public function Euler() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            tr(solve(10000));
//            tr(solve(5678027));
//            tr(solve(7208785));
//            tr(N2.add(solve(5678027), solve(7208785)));
            var g : int = getTimer();
            tr((g - s) + " ms");
        }
        
        // N-2~N+2列目の素数を区間篩で列挙した後、
        // N列目の素数で、隣接する素数の数を数える。
        // 2個以上だったら即採用、
        // 1個以上の場合は、 隣接素数のどれかが、2個以上と隣接してれば採用。
        // 区間篩以外の箇所はすべて二分探索なので、実質区間篩がボトルネック。
        private function solve(N : uint) : Array
        {
        		var sup : Number = (N + 2) * (N + 3) / 2 + 1;
        		var inf : Number = (N - 3) * (N - 2) / 2 + 1;
        		var primes : Array = sieveEratosthenes(Math.sqrt(sup) + 1);
        		var segment : Array = sieveSegment2(inf, sup, primes);
        		
        		var start : Number = N * (N + 1) / 2 - (N - 1);
        		var end : Number = N * (N + 1) / 2;
        		var indStart : int = binarySearch(segment, start);
        		if(indStart < 0)indStart = -indStart-1;
        		var indEnd : int = binarySearch(segment, end+1);
        		if(indEnd < 0)indEnd = -indEnd-1;
//        		tr(segment, start, end);
tr(start, end);
        		
        		var sum : Array = [0, 0];
        		
        		// N列目を調査
        		var qpts : Array = [];
        		var neigh : Array = getNeigh(N);
        		for(var i : uint = indStart;i < indEnd;i++){
        			var p : Number = segment[i];
        			var oks : Array = [];
        			for each(var nei : Number in neigh){
        				if(p == start && (nei == -N || nei == N - 1))continue; 
	        			if(binarySearch(segment, p + nei) >= 0){
	        				oks.push(p + nei);
  	      			}
        			}
        			if(oks.length == 1){
        				// 1個だけ隣接しているのはqptsに入れる
        				qpts.push([p, oks]);
        			}else if(oks.length >= 2){
        				// 2個以上は即採用
//        				tr("P", p, oks);
					N2.inc(sum, p);
        			}
        		}
        		
        		// 隣接項を調査。
        		var neighD : Array = getNeigh(N - 1);
        		var neighU : Array = getNeigh(N + 1);
        		for each(var qpt : Array in qpts){
        			for each(var pn : Number in qpt[1]){
	        			var okct : uint = 1; // 元の素数(qpt[0])の分
	        			for each(nei in pn > qpt[0] ? neighU : neighD){
	        				if(pn + nei == qpt[0])continue; // 元の素数(qpt[0])の分
	        				if(pn == start - (N - 1) && (nei == -(N-1) || nei == (N-1) - 1))continue; 
	        				if(pn == start + N && (nei == -(N+1) || nei == (N+1) - 1))continue; 
		        			if(binarySearch(segment, pn + nei) >= 0){
//		        				tr(pn + nei);
		        				okct++;
	  	      			}
	        			}
	        			if(okct >= 2){
	        				// 2個以上隣接していたら採用
//	        				tr("Q", qpt[0]);
						N2.inc(sum, qpt[0]);
//	        				sum += qpt[0];
	        				break;
	        			}
        			}
        		}
        		
        		return sum;
        }
        
        // 隣接する奇数の相対的位置を取得
        private static function getNeigh(N : Number) : Array
        {
        		return N%2 == 0 ? [-N, -N+2, N] : [-N+1, N-1, N+1];
        }
        
        private static function binarySearch(a : Array, v : Number) : int
        {
        		var s : uint = 0;
        		var g : uint = a.length;
        		if(v > a[g-1])return -g-1;
        		if(v <= a[0])return -1;
        		if(v == a[0])return 0;
        		do{
	        		var m : uint = (s + g) >> 1;
	        		if(v == a[m])return m;
	        		if(v < a[m]){
	        			g = m;
	        		}else{
	        			s = m;
	        		}
        		}while(g - s > 1);
        		return -s - 2;
        }
        
        // 区間篩改良版(2をあらかじめ除いてある)
        private function sieveSegment2(start : Number, end : Number, primes : Array) : Array
        {
        		var sss : Number = start - (start % 2) + 1;
        		var eee : Number = end + 2 - (end % 2 || 2);
        	
        		var ar : Vector.<uint> = new Vector.<uint>((eee - sss) / 2);
        		var i : uint;
        		for(i = 0;i < ar.length;i++)ar[i] = 1;
        		for each(var p : uint in primes){
        			if(p == 2)continue;
        			if(p * p >= end)break;
        			
        			var ssss : uint = p - (sss % p || p);
        			if(ssss & 1){
        				ssss = (p + ssss) >>> 1;
        			}else{
        				ssss >>>= 1;
        			}
        			for(i = ssss;i < ar.length;i += p){
        				ar[i] = 0;
        			}
        		}
        		
        		var ret : Array = [];
        		for(i = 0;i < ar.length;i++){
        			if(ar[i] == 1){
        				var num : Number = sss + i * 2;
        				ret.push(num);
        			}
        		}
        		return ret;
        }

        // 区間篩
        private function sieveSegment(start : Number, end : Number, primes : Array) : Array
        {
        		var ar : Vector.<uint> = new Vector.<uint>(end - start);
        		var i : uint;
        		for(i = 0;i < end - start;i++)ar[i] = 1;
        		for each(var p : uint in primes){
        			if(p * p >= end)break;
        			
        			for(i = (p - (start % p)) % p;i < end - start;i += p){
        				ar[i] = 0;
        			}
        		}
        		
        		var ret : Array = [];
        		for(i = 0;i < end - start;i++){
        			if(ar[i] == 1){
        				ret.push(start + i);
        			}
        		}
        		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;
	}
}