ルジャンドル記号

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

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    public class Test extends Sprite {
        private var _tf : TextField;
  
        public function Test() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            
            var N : Number = Math.pow(10, 11);
            
            /*
            var primes : Array = doEratosthenes(N / 7 / 13 / 19 / 31);
            var p : uint = primes[primes.length - 8];
            tr(p, N/7/13/19/31);
            var u : uint = ((p+1)*(p+1)/4-1)%p;
            tr(u, p);
            tr(calcLegendreCore(u, p));
            */
            
            var i : uint;
            var p : uint = 64*7*13*19*31;
            var ct : uint = 0;
            for(i = 2;i < p;i++){
//                if((i * i * i) % p == 1){
                if((((i * i) % p) * i) % p == 1){
//                if((i * i + i + 1) % p == 0){
                    ct++;
//                    tr(i, i * i * i);
                }
            }
            tr("ct", ct);
            
            var g : int = getTimer();
            tr((g - s) + " ms");
        }

        // (a,b)=1, b:odd prime
        private function calcLegendreCore(a : uint, b : uint) : int
        {
//            tr(a, b);
            if(a == 1){
                return 1;
            }
            
            // Jacobi symbol
            if(a == 2){
                return (b % 8 == 1 || b % 8 == 7) ? 1 : -1;
            }
            if(a == b - 1){
                return b % 4 == 1 ? 1 : -1;
            }
            
            var ret : int = 1;
            if(a < b){
                // Quadratic Reciprocity
                if(a % 2 == 1 && b % 2 == 1 && isPrime(a) && isPrime(b)){
                    var c : uint = a; a = b; b = c;
                    if(a % 4 == 3 && b % 4 == 3){
                        ret = -ret;
                    }
                }
            }
            a %= b;
            
            for(var i : uint = 2;i * i <= a;i++){
                for(var ct : uint = 0;a % i == 0;ct++){
                    a /= i;
                }
                if(ct % 2 == 1){
                    ret *= calcLegendreCore(i, b);
                }
            }
            if(a != 1)ret *= calcLegendreCore(a, b);
            return ret;
        }
        
        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];
            
            var sq : int = Math.sqrt(n);
            for(var i : int = 3;i <= sq;i+=2){
                if(n % i == 0){
                    _cache[n] = false;
                    return false;
                }
            }
            _cache[n] = true;
            return true;
        }
        
        private function doEratosthenes(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");
        }
    }
}