快速的算出一個數是否是質數的方法

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

方法一、用試除法判斷一個自然數a是不是質數時,用各個質數從小到大依次去除a,如果到某一個質數正好整除,這個a就可以斷定不是質數；如果不能整除,當不完全商又小於這個質數時,就不必再繼續試除,可以斷定a必然是質數．

方法二、只要找出x為一個奇數和一個偶數平方差的形式（這是一定的）便可以a2-b2=(a+b)(a-b)便是兩個因數.

例如26341,先找出比26341大的一個偶平方數,26896,與它的差是555,肯定不是平方數,再下一個平方數（其實考慮到(x+1)^2=x2+2x+1,因此直接將原數加上2x+1就行了,用不著算x+1的平方）,27556,差1215,也不是,然後28224個位與1的差為3,直接排除,下一個2559也不是（一看就知道它等於50^2+59）.再下個差為3直接排出,再下個、再再下個……找出規律來就很快了,最後221^2=48841,48841-26341=22500,很明顯22500=150^2,就分解出來了26341=71×371