波波桑
根據數的不同範圍和要求，我總結主要有三種常用的方法判斷一個數是否是素數
一. 一般方法
直接判斷在sqrt(n)範圍內有沒有整數能整除n，如果有則不是素數，否則就是素數。
但這種方法比較暴力，如果n過大是不行的，而且一個一個去計算太慢了，如果我要找出10000000以內的所有素數，那計算量是相當大，效率不高。
二. 基於線性篩法
如果要找出10000000以內的所有素數，那麼就要使用線性篩法了。基本原理是：先把所有整數列出來，然後把2的倍數全部剔除，然後是三的，以此類推，遍歷所有素數，把倍數全部劃去。劃去的是合數，剩下的就是素數了。
那麼，如果n特別大的時候呢，比如n=10^12，又怎麼判斷呢？ 這時候就需要Miller-Rabin素數測試方法了。
三. Miller-Rabin素數測試
它是基於二次探測定理進行判斷的，定理描述如下
代碼實現比較長，截圖在下面
一般情況下第二種和第三種方法用得最多。
薛定諤的小貓貓
如何判斷一個數是素數，而且還要求快速，比如給一個數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那個函數。
看懂了的，記得給一個贊，聽說點讚的小夥伴都走上了人生巔峰。不懂的評論區見。
波波桑
我們要判斷一個數是素數，就要排除所有小於這個數的素數是該數的因數。沒有“更巧妙”的方法。
然而，我們有一個規律可資利用，這樣可以減少工作量：一個數N，我們可以只試驗比“根號N”小的所有素因數，而不必試驗所有比N小的素因數。
bratskid
一個小循環就可以了
南陽理工14軟件
不知道現在世界上不用計算機，最先進判定質數的方法是什麼，我自以為有較先進的方法。比如已知1萬內所有質數，分解58965539是質還是合。要多長時間。
