謝邀，抽時(shí)間速度答題,。

如何判斷一個(gè)數(shù)是素?cái)?shù),，而且還要求快速，比如給一個(gè)數(shù)N,，判斷數(shù)N是否是素?cái)?shù),，該怎么做呢？

質(zhì)數(shù)（prime number）又稱素?cái)?shù),，有無限個(gè),。質(zhì)數(shù)定義為在大于1的自然數(shù)中，除了1和它本身以外不再有其他因數(shù),，這樣的數(shù)稱為質(zhì)數(shù),。

它的因素只有1和它本身，而在所有實(shí)數(shù)集合中,，這樣的素?cái)?shù)有無數(shù)個(gè),。

那么一般的方法可以用下面的這種方法來計(jì)算，通過尋找所有的因數(shù),，但是這種方法其實(shí)當(dāng)n這個(gè)數(shù)很大的時(shí)候是很慢的,。那么有沒有更快的方法呢,？答案是必須的。

費(fèi)馬小定理

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

有這個(gè)費(fèi)馬小定理以后,，再回去看看這個(gè)判斷素?cái)?shù)的問題,，是否可以用費(fèi)馬小定理來解決呢,？先來看一個(gè)HOJ的題目,，題目鏈接在這兒：

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

題目大意就是，給你一個(gè)正整數(shù),，需要你編一個(gè)程序,，去判斷這個(gè)數(shù)是不是素?cái)?shù)。

既然讓你判斷是不是素?cái)?shù),，如果你用最上面的那個(gè)很原始的方法去,，必然Time out，這個(gè)時(shí)候就需要用到費(fèi)馬小定理了,，先來看看我N年輕寫的代碼,。

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

看懂了的,，記得給一個(gè)贊，聽說點(diǎn)贊的小伙伴都走上了人生巔峰,。不懂的評(píng)論區(qū)見,。