质数递回排序二分搜树-建中首页

質數(Prime) 如同大家所熟知的,質數就是一個正因數只有1和自己的正整數。 在寫程式時,我們要如何快速的找出質數呢? 最直觀的方法就是直接依照質數的定義去做。把所有大於一小於他的正整數全部拿來除除

質數(Prime) 如同大家所熟知的,質數就是一個正因數只有1和自己的正整數。 在寫程式時,我們要如何快速的找出質數呢? 最直觀的方法就是直接依照質數的定義去做。把所有大於一小於他的正整數 全部拿來除除看,如果都不能整除它那麼它就是個質數。 這方法在只問你某個數是不是質數的時候還可以用,但若要建立質數表的時候 就非常緩慢了。 #想一想:真的需要把該數以下的所有數都拿來除,才能知道它是不是質數嗎? Eratosthenes’篩法 兩千多年前,一個古希臘的數學家Eratosthenes就已經知道如何有效率的建 立一個質數表了。 這個演算法的想法就是說,假如我們把正整數排成一列,由小到大去看,每看到 一個質數就把它的所有倍數刪掉,這樣就可以列出一張1~n的質數表了。 #想一想:要如何加快篩法的速度呢? 1.對於質數p,可以從多少開始篩? 2.需要篩到多大的質數才夠呢? ↗相關題目:TIOJ1036 質因數分解