Project Euler 131

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

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=131
    public class Euler131 extends Sprite {
        private var _tf : TextField;
  
        public function Euler131() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            _tf.appendText(solve(1000000).toString() + "\n");
            var g : int = getTimer();
            _tf.appendText((g - s).toString() + " ms\n");
        }
        
        // まず、n=a^3の形に書ける。(aは自然数)
        // 明らかにnはpの倍数でないので、nの素因数はpと互いに素。
        // よって、n+pはnの素因数を含まないのでn^2(n+p)が立方数であるためには、nが同じ素因数をつねに3の倍数個持っていなければならない。
        
        // n^3+n^2p=m^3 (mは自然数)を変形して
        // p = m^3/n^2 - n = (m/a^2)^3 - a^3
        //   = k^3 - a^3    (k = m/a^2)
        //   = (k-a)(k^2+ak+a^2)
        // k^2+ak+a^2 > 1なので、
        // k-a=1, k^2+ak+a^2=pとなり、
        // p=3a^2+3a+1, m=a^3+a^2
        
        // つまり、a>=1について、p=3a^2+3a+1が素数であるものをp<=1000000で数えていけばよい。
        private function solve(N : int) : int
        { 
            var ct : int = 0;
            for(var a : int = 1;;a++){
                var p : int = 3 * a * a + 3 * a + 1;
                if(p > N)break;
                if(doMillerRabin(p)){
                    ct++;
                }
            }
            return ct;
        }
        
        private static function doMillerRabin(n : int) : Boolean
        {
            for(var d : int = n - 1, s : int = 0;(d & 1) == 0;d >>= 1, s++);
            for each(var a : Number in [2, 7, 61]){
                if(n <= a)continue;
                var ad : Number = 1;
                for(var i : int = d;i > 0;i >>= 1){
                    if((i & 1) == 1){
                        ad *= a;
                        ad %= n;
                    }
                    a *= a;
                    a %= n;
                }
                if(ad != 1){
                    for(var r : int = 0;r < s;r++){
                        if(ad == n-1)break;
                        ad *= ad;
                        ad %= n;
                    }
                    if(r == s)return false;
                }
            }
            return true;
        }
    }
}