素数探索

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

// forked from tepe's forked from: 素数を数えて落ち着く
// forked from keno42's 素数を数えて落ち着く
// 素数カウント
package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.events.Event;
    import flash.utils.*;
    public class FlashTest extends Sprite {
        
        private var tf:TextField = new TextField();
        //private var str:String = new String();
        private var s1:Sprite = new Sprite();
        
        public function FlashTest() {
            // write as3 code here..
            
            addChild(s1);
            s1.y = 450;
            s1.graphics.lineStyle(0,0x0000ff,0.9);
            

            addChild(tf);
            tf.height = 465;
            tf.width = 465;
            tf.multiline=true;        
            
            init();
            addEventListener(Event.ENTER_FRAME, onEnterFrame);
        }

        private var cnt:int=0;
        private var size:int = 1000;//１回で探索する数 
        private var time:int//時間計測
        private function onEnterFrame(e:Event=null):void{
            
            cnt++;
            //if(cnt%30 != 0)return;//処理速度調整
            
            var st:int = getTimer();//処理時間計測
            for(var i:int=0;i<size;i++){
                while(!func4()){}
            }
            
            var end:int = getTimer(); 
            time = end - st;
            draw();
            
        }
        
        

        
        private var list:Vector.<uint> = new Vector.<uint>();//素数リスト
        private var n:int=0;//判定する整数
        
        //素数探索1
        private function func1():Boolean{
            n++;
            
            //リスト内の素数に引っかからなければ追加
            for(var i:uint=0;i<list.length;i++){              
                if(0 == n % list[i] )return false;//index が 素数の倍数なら終了
            }
            list.push(n);
            return true;
        
        }
        
        //素数探索2
        private function func2():Boolean{
            n++;
            
            //リスト内の素数に引っかからなければ追加
            //リストの素数すべてを試す必要はない
            for(var i:uint=0;i<list.length;i++){               
                if(0 == n % list[i] )return false;//index が 素数の倍数なら終了
                else if(n/list[i]<list[i])break;//これより大きい倍数の可能性はないので省略
            }
            list.push(n);
            return true;
        
        }
        
        
        //素数探索3
        private var limit:uint = 0;
        private function func3():Boolean{
            n++;

            //リスト内の素数に引っかからなければ追加
            for(var i:uint=0;i<=limit;i++){
                if(0 == n % list[i] )return false;//index が 素数の倍数なら終了
            }
            list.push(n);
            if( list[limit]*list[limit] < n ) limit++;
            return true;
        }
        
        //２の倍数での処理を省略
        private function init():void{
            list.push(2);
            n = 1;
        }
        private function func4():Boolean{
            n+=2;

            //リスト内の素数に引っかからなければ追加
            for(var i:uint=1;i<=limit;i++){
                if(0 == n % list[i] )return false;//index が 素数の倍数なら終了
            }
            list.push(n);
            if( list[limit]*list[limit] < n ) limit++;
            return true;
        }
        
        
        private var scale:int=400;
        private var peek:uint=400;
        private function draw():void{
            
            s1.graphics.lineTo(cnt,-(time));
            s1.scaleX = 465/(cnt);
            var val:Number = (time/size)*100;
            if(peek<val)peek=val;
            if(scale<peek){
                scale++;
                s1.scaleY = 400/scale;
            }

            
            
            var str:String = ""; 
            if(0<limit)str += "limit: prime["+limit.toString()+"] = "+list[limit].toString()+"\n";
            var len:int = 30;
            if(list.length<30)len=list.length;
            for(var i:int=list.length-len;i<list.length;i++){                
                str += "prime["+i.toString()+"] = "+list[i].toString()+"\n";
            }
            

            tf.text = str;
        }

        


    }
}