引理：如果 a 是一個(gè)大于1的整數(shù)，而所有小于或等于根號(hào) a  的素?cái)?shù)都除不盡 a ，則 a 是素?cái)?shù)。
理想的判斷素?cái)?shù)的方法應(yīng)該是將所有小于或等于根號(hào)n的素?cái)?shù)去除n，但是n是一個(gè)隨機(jī)大于1的整數(shù)，小于這個(gè)數(shù)的平方根的素?cái)?shù)表不好給定。下面介紹的方法，本意是動(dòng)態(tài)的構(gòu)建素?cái)?shù)表，但是引入了很多冗余的除數(shù)。

代碼：

分析：
　　相對(duì)于sqrt(n)次除，上面的程序需要sqrt(n)*8/30次除，效率提升了15/4倍。
　　自然數(shù)n，我們假設(shè)小于n的素?cái)?shù)數(shù)F(n),F(n)的分布規(guī)律為：當(dāng)n趨向于無(wú)窮大時(shí)，F(xiàn)(n)/(x/logx) = 1;
        所以，動(dòng)態(tài)的冗余度近似為：(sqrt(n)*4/15-x/logx)/sqrt(n)*4/15

其他更好的判斷素?cái)?shù)的算法，希望你能給我留言或者寫(xiě)在評(píng)論上，謝謝！