如何算出質數的好方法

⑴ 如何判斷質數

判斷質數的最快方法如下：

1、查表法：

主要是指查「質數表」。

編制質數表的過程是：按照自然數列，第一個數1不是質數，因此要除外，然後按順序寫出2至100的所有自然數，這些數中2是質數，把它留下，把2後面所有2的倍數劃去，2後面的3是質數，接著再把3後面所有3的倍數劃去，如此繼續下去，剩下的便是100以內的全部質數。

2、試除法：

在手頭上沒有質數表的情況下，可以用試除法來判斷一個自然數是不是質數。例如判斷143、179是不是質數，就可以按從小到大的順序用2、3、5、7、11……等質數去試除。一般情況下用20以內的2、3、5、7、11、13、17、19這8個質數去除就可以了。

原理簡析：由合數的意義可知，只要判斷一個數除了1和它本身還有別的因數，這個數就是合數。因為因數是成對出現的，所以只要判斷前一半即可。10^2=100，而10以內的質數只有2、3、5、7，所以只要劃掉2、3、5、7的倍數即可（2、3、5、7除外）。

重點來了！2、5的倍數一眼就能看出，3的倍數只需計算數字和（1位數+1位數），7的倍數除去2、3、5的倍數及九九表內的數，只剩下77和91，而77又可以一眼看出是合數，所以只剩一個數——91！

簡單歸納一下：100以內除了91，個位數字是1、3、7、9的，數字和不是3的倍數的都是質數。

舉個例子，79

第一秒，不是九九表內數字，不是2、5的倍數，不是77、91；

第二秒，7+9=16，不是3的倍數。

第三秒，機動時間、檢查時間。

⑵ 如何判斷質數的方法

判斷一個數是否為質數，常見的方法有以下幾種：

1. 最大因數法：

   • 嘗試尋找一個數的最大因數。
   • 若該數的最大因數為它本身，則為質數。

2. 平方根法則：

   • 計算該數的平方根，取其整數部分。
   • 若整數部分大於1且小於該數本身，則該數非質數。
   • 若整數部分小於等於1，則該數為質數。

3. 因子表法：

   • 構建一個從2到該數平方根的因數表。
   • 檢查該數是否有除1和自身外的因數。
   • 若無，則該數為質數。

注意：以上方法適用於多數情況下的質數判斷。在處理較大數時，由於計算量較大，可以使用更高效的演算法，如米勒拉賓素性檢驗、費馬檢驗等。