Project Euler 200

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

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=200
    public class Euler200 extends Sprite {
        private var _tf : TextField;
  
        public function Euler200() {
            _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
        {
        		var i : uint, j : uint;
        		var primes : Array = sieveEratosthenes(250000);
        		var tops : Array = [];
        		var ct : uint = 0;
        		// 小さい数を列挙しやすいものから消していく。
        		// 2, 5の倍数はprime-proofの判定が1の位だけでいいので、
        		// それを先に洗う。
        		
        		var p : uint;
        		var n : Number;
        		var base : Number;
        		var f : Boolean;
        		var x : uint;
        		
        		// p^2 * 2^3
        		for each(p in primes){
        			n = p * p * 8;
        			if(n.toString().indexOf("200") > -1){
        				base = n - (n % 10);
        				f = true;
        				for each(x in [1, 3, 7, 9]){
        					if(isPrime(base + x)){
        						f = false;
        						break;
        					}
        				}
        				if(!f)continue;
        				ct++;
        				tops.push({number:n, p2:p, p3:2});
        				if(ct == 200)break;
        			}
        		}
        		
        		// 2^2 * p^3
        		for each(p in primes){
        			n = p * p * p * 4;
        			if(n > tops[199].number)break;
        			if(n.toString().indexOf("200") > -1){
        				base = n - (n % 10);
        				f = true;
        				for each(x in [1, 3, 7, 9]){
        					if(isPrime(base + x)){
        						f = false;
        						break;
        					}
        				}
        				if(!f)continue;
        				tops.push({number:n, p2:2, p3:p});
        			}
        		}
        		
        		tops.sortOn("number", Array.NUMERIC);
        		tops = tops.slice(0, 200);
        		
        		// p^2 * 5^3
        		for each(p in primes){
        			if(p == 2 || p == 5)continue;
        			n = p * p * 125;
        			if(n > tops[199].number)break;
        			if(n.toString().indexOf("200") > -1){
        				base = n - (n % 10);
        				f = true;
        				for each(x in [1, 3, 7, 9]){
        					if(isPrime(base + x)){
        						f = false;
        						break;
        					}
        				}
        				if(!f)continue;
        				ct++;
        				tops.push({number:n, p2:p, p3:5});
        				if(ct == 200)break;
        			}
        		}
        		tops.sortOn("number", Array.NUMERIC);
        		tops = tops.slice(0, 200);
        		printTops(tops);
        		
        		// 5^2 * p^3
        		for each(p in primes){
        			if(p == 2 || p == 5)continue;
        			n = p * p * p * 25;
        			if(n > tops[199].number)break;
        			if(n.toString().indexOf("200") > -1){
        				base = n - (n % 10);
        				f = true;
        				for each(x in [1, 3, 7, 9]){
        					if(isPrime(base + x)){
        						f = false;
        						break;
        					}
        				}
        				if(!f)continue;
        				ct++;
        				tops.push({number:n, p2:5, p3:p});
        				if(ct == 200)break;
        			}
        		}
        		tops.sortOn("number", Array.NUMERIC);
        		tops = tops.slice(0, 200);
        		printTops(tops);
        		
        		// p^2 * q^3
        		// prime-proofの判定もしているが、実際にprime-proofになるのは
        		// ひとつもなかった。
        		var q : uint;
        		var r : Number;
        		var gct : uint = 0;
        		for each(p in primes){
        			if(p == 2 || p == 5)continue;
        			for each(q in primes){
        				if(q == 2 || q == 5 || p == q)continue;
        				n = p * p * q * q * q;
        				if(n > tops[199].number)break;
	        			if(n.toString().indexOf("200") > -1){
	        				base = n - (n % 10);
	        				f = true;
	        				for each(x in [1, 3, 7, 9]){
	        					if(isPrime(base + x)){
	        						f = false;
	        						break;
	        					}
	        				}
	        				if(!f)continue;
	        				
	        				for(r = 10;r < n;r *= 10){
	        					base = n - uint((n % (r * 10)) / r) * r;
	        					for(i = 0;i <= 9;i++){
	        						if(isPrime(base + i * r)){
	        							f = false;
	        							break;
	        						}
	        					} 
	        					if(!f)break;
	        				}
	        				if(!f)continue;
	        				tr(n, p, q);
	        				gct++;
	        			}
        			}
        		}
        		tr(gct);
        		return 0;
        }
        
        private function printTops(tops : Array) : void
        {
        		for(var i : uint = 0;i < tops.length;i++){
        			var o : Object = tops[i];
        			tr(i, o.number, o.p2, o.p3);
        		}
        }
        
        private var _cache : Object = {};
        private function isPrime(n : Number) : Boolean
        {
            if(n <= 1)return false;
            if(n % 2 == 0)return n == 2;
            if(_cache[n])return _cache[n] == 1;
            
            var sq : int = Math.sqrt(n);
            for(var i : int = 3;i <= sq;i+=2){
                if(n % i == 0){
                    _cache[n] = -1;
                    return false;
                }
            }
            _cache[n] = 1;
            return true;
        }
                
        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;
        }
    }
}