アトキンの篩

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

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);
            
            tr("Atkin:");
            var s : int = getTimer();
            
//            tr(doAtkin(1000000));
            tr(doAtkin(10000000).length);
            var g : int = getTimer();
            tr((g - s) + " ms");
            
            tr("Eratosthenes:");
            s = getTimer();
            tr(doEratosthenes(10000000).length);
            g = getTimer();
            tr((g - s) + " ms");
            
            tr(doAtkin(100));
            tr(doEratosthenes(100));
        }
        
        private function doAtkin(n : int) : Array
        {
            var isPrime : Vector.<Boolean> = new Vector.<Boolean>(n+1);
            var i : int, x : int, y : int, z : int, u : int;
            var sqn : int = Math.sqrt(n);
            for(i = 0;i < isPrime.length;i++)isPrime[i] = false;
            
            for(z = 1;z <= 5;z += 4){
                for(y = z;y <= sqn;y += 6){
                    for(x = 1;x <= sqn && (u = 4*x*x+y*y) <= n;x++){
                        isPrime[u] = !isPrime[u];
                    }
                    for(x = y + 1;y <= sqn && (u = 3*x*x-y*y) <= n;x += 2){
                        isPrime[u] = !isPrime[u];
                    }
                }
            }
            
            for(z = 2;z <= 4;z += 2){
                for(y = z;y <= sqn;y += 6){
                    for(x = 1;x <= sqn && (u = 3*x*x+y*y) <= n;x += 2){
                        isPrime[u] = !isPrime[u];
                    }
                    for(x = y + 1;x <= sqn && (u = 3*x*x-y*y) <= n;x += 2){
                        isPrime[u] = !isPrime[u];
                    }
                }
            }
            
            for(y = 3;y <= sqn;y += 6){
                for(z = 1;z <= 2;z++){
                    for(x = z;x <= sqn && (u = 4*x*x+y*y) <= n;x += 3){
                        isPrime[u] = !isPrime[u];
                    }
                }
            }
            for(u = 5;u <= sqn;u+=2){
                if(isPrime[u]){
                    var step : int = u * u;
                    for(x = step;x <= n;x += step*2){
                        isPrime[x] = false;
                    }
                }
            }
            var ret : Array = [2, 3];
            for(i = 5;i < isPrime.length;i++){
                if(isPrime[i])ret.push(i);
            }
            return ret;
        }
        
        private static function doEratosthenes(n : int) : Array
        {
            var ar : Vector.<uint> = new Vector.<uint>(n / 2 - 1);
            var i : int;
            for(i = 0;i < ar.length;i++)ar[i] = 1;
            
            var sq : int = (Math.sqrt(n) - 3) >> 1;
            for(var p : int = 0;p <= sq;p++){
                if(ar[p] == 1){
                    var m : int = (p << 1) + 3;
                    var m2 : int = m << 1;
                    for(var mm : int = m * m;mm <= n;mm += m2){
                        ar[(mm - 3) >> 1] = 0;
                    }
                }
            }
            var ret : Array = [2];
            for(i = 0;i < ar.length;i++){
                if(ar[i] == 1)ret.push((i << 1) + 3);
            }
            return ret;
        }
        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
        }
    }
}