• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        


            
	
            
		
			

            

            
	
            
		
			
            是技術，更是藝術
            
			一心編程，就沒有解決不了的問題
		            		
	
            

            

            

            

            posts - 9, comments - 11, trackbacks - 0, articles - 0
            


            		
	
            
	
            
		
			
		
		
			
            
				
					
	
            
		
            
			
            
				快速判斷素數算法
			
            
 			Posted on 2010-07-16 21:40 李熙建 閱讀(4237) 評論(3)  編輯 收藏 引用  所屬分類: 算法 
			
			


		
            
		
                引理：如果 a 是一個大于1的整數，而所有小于或等于根號 a  的素數都除不盡 a ，則 a 是素數。
            理想的判斷素數的方法應該是將所有小于或等于根號n的素數去除n，但是n是一個隨機大于1的整數，小于這個數的平方根的素數表不好給定。下面介紹的方法，本意是動態的構建素數表，但是引入了很多冗余的除數。

            代碼：
            

            bool prime (int num)
            {
                          if (num == 2 || num == 3 || num == 5)
                            return true;
                          if (num % 2 == 0 || num % 3 == 0 || num % 5 == 0 || num == 1)
                            return false;

              unsigned             long c = 7;
                          int maxc = int (sqrt (num));
                          while (c <= maxc)
                            {
                              if (num % c == 0)
                                return false;
                  c             += 4;
                              if (num % c == 0)
                                return false;
                  c             += 2;
                              if (num % c == 0)
                                return false;
                  c             += 4;
                              if (num % c == 0)
                                return false;
                  c             += 2;
                              if (num % c == 0)
                                return false;
                  c             += 4;
                              if (num % c == 0)
                                return false;
                  c             += 6;
                              if (num % c == 0)
                                return false;
                  c             += 2;
                              if (num % c == 0)
                                return false;
                  c             += 6;
                }
                          return true;
            }
            

            分析：
            　　相對于sqrt(n)次除，上面的程序需要sqrt(n)*8/30次除，效率提升了15/4倍。
            　　自然數n，我們假設小于n的素數數F(n),F(n)的分布規律為：當n趨向于無窮大時，F(n)/(x/logx) = 1;
                    所以，動態的冗余度近似為：(sqrt(n)*4/15-x/logx)/sqrt(n)*4/15 

            其他更好的判斷素數的算法，希望你能給我留言或者寫在評論上，謝謝！

            
	
            


            
	    
    

            Feedback
            
	
			
            
				
            
					
            
						# re: 快速判斷素數算法  回復  更多評論
						  
					
            
					2011-06-02 20:47 by 某W
				
            
				
            這方法很強大~

            謝謝~
            
			
            
		
			
            
				
            
					
            
						# re: 快速判斷素數算法  回復  更多評論
						  
					
            
					2011-08-01 09:19 by 李熙建
				
            
				
            @某W

            謝謝，拋磚引玉而已，期待你提出更優秀的方法
            
			
            
		
			
            
				
            
					
            
						# re: 快速判斷素數算法  回復  更多評論
						  
					
            
					2012-10-25 19:21 by aa
				
            
				
            理論依據是什么？
            
			
            
		




            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



精品久久久无码人妻中文字幕豆芽|
亚洲精品成人网久久久久久|
久久精品九九亚洲精品|
精品国产乱码久久久久久1区2区|
国产一级持黄大片99久久|
久久婷婷综合中文字幕|
蜜桃麻豆WWW久久囤产精品|
久久精品国产一区二区三区日韩|
青青草原综合久久大伊人精品|
伊人热热久久原色播放www|
久久久精品人妻一区二区三区蜜桃|
久久久久亚洲AV无码去区首|
人妻无码中文久久久久专区|
欧美无乱码久久久免费午夜一区二区三区中文字幕
|
久久无码国产专区精品|
精品久久久久久中文字幕人妻最新|
久久精品这里只有精99品|
久久精品www人人爽人人|
久久这里只有精品久久|
激情综合色综合久久综合|
丁香五月综合久久激情|
亚洲AV乱码久久精品蜜桃|
久久综合亚洲色HEZYO国产|
久久AV高清无码|
精品久久久中文字幕人妻|
亚洲国产精品久久|
久久99久久99精品免视看动漫|
人妻无码精品久久亚瑟影视|
噜噜噜色噜噜噜久久|
久久综合九色欧美综合狠狠
|
久久免费小视频|
国内精品九九久久久精品|
亚洲va久久久噜噜噜久久男同|
亚洲日本久久久午夜精品|
久久久久亚洲精品无码网址
|
色欲久久久天天天综合网|
一级A毛片免费观看久久精品|
久久久久国色AV免费观看|
久久av免费天堂小草播放|
国内精品久久久久久久久
|
国产毛片欧美毛片久久久|