如何快速判斷一個數是素數？

謝邀，抽時間速度答題。

如何判斷一個數是素數，而且還要求快速，比如給一個數N，判斷數N是否是素數，該怎么做呢？

質數（prime number）又稱素數，有無限個。質數定義為在大于1的自然數中，除了1和它本身以外不再有其他因數，這樣的數稱為質數。

它的因素只有1和它本身，而在所有實數集合中，這樣的素數有無數個。

那么一般的方法可以用下面的這種方法來計算，通過尋找所有的因數，但是這種方法其實當n這個數很大的時候是很慢的。那么有沒有更快的方法呢？答案是必須的。

費馬小定理

費馬小定理(Fermat's little theorem)是數論中的一個重要定理，在1636年提出，其內容為： 假如p是質數，且gcd(a,p)=1，那么 a^(p-1)≡1（mod p），即：假如a是整數，p是質數，且a,p互質(即兩者只有一個公約數1)，那么a的(p-1)次方除以p的余數恒等于1。

有這個費馬小定理以后，再回去看看這個判斷素數的問題，是否可以用費馬小定理來解決呢？先來看一個HOJ的題目，題目鏈接在這兒：

http://acm.hit.edu.cn/hoj/problem/view?id=1356

題目大意就是，給你一個正整數，需要你編一個程序，去判斷這個數是不是素數。

既然讓你判斷是不是素數，如果你用最上面的那個很原始的方法去，必然Time out，這個時候就需要用到費馬小定理了，先來看看我N年輕寫的代碼。

下面來講講這個答案哈。費馬小定理里面講到，假如p是質數，且gcd(a,p)=1，那么 a^(p-1)≡1（mod p），即：假如a是整數，p是質數，且a,p互質(即兩者只有一個公約數1)，那么a的(p-1)次方除以p的余數恒等于1。也就是說我們sample幾個素數a，去驗證整個p，如果滿足了費馬小定理，那么這個p是素數的可能性非常非常的大。具體需要sample幾個，這個貌似有正面，其實3-4個基本上就滿足了，非素數是很容易就被檢測出來的。其實這個問題就轉換為如何去快速的算次方和模運算了，恰恰有一個理論叫做蒙哥馬利冪模運算，具體這個方法可以去網上自己搜一下，也就是對應我們代碼里面的mod那個函數。

看懂了的，記得給一個贊，聽說點贊的小伙伴都走上了人生巔峰。不懂的評論區見。