Project Euler 214

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

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=214
    public class Euler214 extends Sprite {
        private var _tf : TextField;
  
        public function Euler214() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            _tf.appendText("" + solve(40000000, 25) + "\n");
            var g : int = getTimer();
            _tf.appendText("" + (g - s) + " ms\n");
        }
        
        private var _primes : Array;
        
        private function solve(N : int, ct : int) : Number
        {
            _primes = doEratosthenes(N);
            var cache : Object = {};
            var sum : Number = 0;
            var pinf : int = 1 << (ct - 2);
            for each(var p : int in _primes){
                if(p < pinf)continue;
                for(var i : int = 1, q : int = p - 1;i < ct - 1 && q > 1;i++){
                    if(cache[q]){
                        q = cache[q];
                        continue;
                    }
                    var t : int = totient(q, _primes);
                    cache[q] = t;
                    q = t;
                }
                if(i == ct - 1 && q == 1){
                    sum += p;
//                    _tf.appendText("" + p + "\n");
                }
            }
            return sum;
        }
        
        private function step(seed : Array) : Array
        {
            var prev : Array = seed.concat();
            for each(var p : int in _primes){
                if(p - 1 > prev[prev.length - 1])break;
                var l : int = prev.length;
                for(var i : int = 0;i < l;i++){
                    if(prev[i] % (p - 1) == 0){
                        prev.push(int(prev[i] / (p - 1)) * p);
                    }
                }
            }
            
            var map : Object = {};
            for each(var s : int in prev){
                if(seed.indexOf(s) == -1){
                    map[s] = s;
                }
            }
            
            var ret : Array = [];
            for each(var q : int in map){
                ret.push(q);
            }
            
            return ret;
        }
        
        private static function totient(n : int, primes : Array) : int
        {
            var ret : int = n;
            var sq : int = Math.sqrt(n);
            for each(var p : int in primes){
                if(sq < p)break;
                if(n % p == 0){
                    ret /= p;
                    ret *= p - 1;
                    while(n % p == 0)n /= p;
                    sq = Math.sqrt(n);
                }
            }
            if(n != 1){
                ret /= n;
                ret *= n - 1;
            }
            return ret;
        }
        
        private static function enumTotient(n : int, primes : Array) : Array
        {
            var ar : Array = new Array(n + 1);
            var i : int;
            for(i = 1;i <= n;i++)ar[i] = i;
            for each(var p : int in primes){
                for(i = p;i <= n;i += p){
                    ar[i] /= p;
                    ar[i] *= p - 1;
                }
            }
            
            return ar;
        }
        
        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;
        }
        }
}