有什麼方法或是小竅門可以迅速辨別一個多位數（小於10位大於3位）是否是質數？

12-03

在《數字——破解萬物的鑰匙》里第102頁有列出了檢驗一個數是否可以被2到13之間的數整除的方法。不過題目是判斷質數的方法，所以用從2到 $sqrt{n}$ （向下取整）之間的質數去試除即可。因為如果連質數都不能分解一個數，那麼合數也不能。經改編、精簡如下：
編者註：當且僅當條件成立時，才滿足被對應的數整除。

2：末位是0、2、4、6、8中的一個。
3：數字根（各位數字和）能被3整除。可遞歸使用。如273，2+7+3=12。問題轉換為12能否被3整除。因為1+2=3，3能整除於3，所以273能被3整除。
5：末位是0或5。
7：用該數的個位乘以2，求得一個積，用剛才剩餘的其他位數減去這個積。差能被7整除或為0。可遞歸使用。如273，27-3*2=21。問題轉換為21能否被7整除。因為2-1*2=0，所以273能被7整除。
11：把加號和減號交替插入該數各位間，和能被11整除或為0。可遞歸使用。如1848，+1-8+4-8=-11，問題轉換為11能否被11整除。因為+1-1=0，所以1848能被11整除。
13：用該數各位乘以9，然後用剩餘的前幾位數相減，差能被13整除。可遞歸使用。如2184，218-4*9=182，18-2*9=0，所以2184能被13整除。
19：用末尾兩位數乘以4，然後把積與其他位相加，和能被19整除。可遞歸使用。如6935，69+35*4=209，2+09*4=38，38能被19整除，所以6935能被19整除。

出於抖機靈的目的口算的話，一般要麼遇到的數有個個位或者兩位數的因子，暴力試試就好了。雖然有各種秘訣，但是其實2,3,5的大家都會，1001=7*11*13一下解決三個連號的很超值，別的直接暴力除法得了，不會比什麼秘訣慢多少的。

要麼是兩個特別接近的數的乘積，你算個平方根在兩邊抖抖就好了。（(x+a) * (x-a) = x^2-a^2 可以幫上忙，反正大質數的差都是偶數）

對於那種 5xxxxxxxx = 1xxxx * 4xxxx 的合數，你就認了吧，咱不是研究口算的。

Miller rabin固然好，一來並沒有辦法口算，二來你發現不是質數以後你沒法給出分解，百口莫辯。

從演算法角度來考慮這個問題。
準確演算法，把2到 $sqrt{n}$ 都試除一遍，顯然這太慢了。
當然，如果有很多次詢問的話我們會使用篩法，這可以做到線性時間複雜度。
可這還是太慢了，或者我們只需要考慮單個詢問~
於是我們就得祭出一些不一定對但是快而且很有可能是對的演算法。
首先介紹費馬小定理，即如果 $P$ 是一個素數，那麼對任意整數 $x$ ，有
$x^{p-1} equiv 1(mod P)$
所以如果能找到一個 $x$ 讓這個等式跪掉， $P$ 明顯就是合數。
更神的是，如果我們只用 $x=2$ 來測試一下，大多數時候也是對的。
大多數時候是什麼意思呢，算導說了：前一萬裡面只有22個數會跪掉。
但我們還是想改進這個演算法，於是我們祭出了另一個神器Miller-Rabin，它做了如下改進
1、隨機多選幾個底數去試試。
2、設 $P$ 為大於等於 $5$ 的素數，那麼 $P-1$ 是偶數，因此我們可以把 $P-1$ 里的所有 $2$ 都提出來，寫成這樣 $P-1=2^{s}r$ ，為什麼要這樣呢，因為我們要考慮數列：
$a^{s} mod P \ a^{2s} mod P \ a^{4s} mod P\ ..................\ a^{P-1} mod P$
最後一個數顯然是1，那麼顯然倒數第二個數一定是 $P-1$ 。
換個說法，如果這個數列里除了最後一個數以外出現了 $-1$ 或者 $1$ ，恭喜你，不用算了，最後一個數一定是 $1$ 。
代碼如下

//以a為基,n-1=x*2^t a^(n-1)=1(mod n) 驗證n是不是合數 //一定是合數返回true,不一定返回false bool check(long long a,long long n,long long x,long long t) { long long ret=pow_mod(a,x,n); long long last=ret; for(int i=1;i&<=t;i++) { ret=mult_mod(ret,ret,n); if(ret==1last!=1last!=n-1) return true;//合數 last=ret; } if(ret!=1) return true; return false; } // Miller_Rabin()演算法素數判定 //是素數返回true.(可能是偽素數，但概率極小) //合數返回false; bool Miller_Rabin(long long n) { if(n&<2)return false; if(n==2)return true; if((n1)==0) return false;//偶數 long long x=n-1; long long t=0; while((x1)==0){x&>&>=1;t++;} for(int i=0;i&

額，至於現在的出錯率嘛，看到第二個函數里的變數S了嗎？顯然是和這玩意有關的。算導的結論是對一個奇數出錯的概率至多為。具體證明可以去看算導，如果覺得算導看不懂可以去看劉汝佳的《演算法藝術與信息學競賽學習指導》。什麼，你說Adleman Pomerance和Rumely在《Annals of Mathematics》那個確定性的演算法？我不會啊~~么么噠~ 等等~這個問題是和最強大腦有關的？看來是時候放棄RSA了


樓上好多都說到了，用miller-rabin演算法可以以很大概率正確判斷一個數是否是素數，可以考慮選擇合適的底數避免錯誤，也就是下面這個函數中的a，原作者使用的隨機生成著作權歸作者所有。

商業轉載請聯繫作者獲得授權，非商業轉載請註明出處。

作者：王雪竹

鏈接：https://www.zhihu.com/question/23477631/answer/25918437

來源：知乎

bool check(long long a,long long n,long long x,long long t)

{

    long long ret=pow_mod(a,x,n);

    long long last=ret;

    for(int i=1;i&<=t;i++)
    {
        ret=mult_mod(ret,ret,n);
        if(ret==1last!=1last!=n-1) return true;//合數
        last=ret;
    }
    if(ret!=1) return true;
    return false;
} 

如果選擇三個底數2, 7和61，那麼被測數小於4 759 123 141都不會出錯
如果選擇(2, 3, 5, 7, 11, 13和17)進行測試，所有不超過341 550 071 728 320都不會出錯
如果選用2, 3, 7, 61和24251作為底數，那麼10^16內唯一出錯的數為46 856 248 255 981
在公交車上沒事的時候，我經常看著來往的車輛的車牌號，然後分解質因數，漸漸地對一些數是否為質數有了感覺，所以斗膽來回答這一題。
完全、迅速地判斷一個大數是不是質數是很困難的，基本上沒有比篩法更好的方法了，計算機運算的話即使是10位數也肯定在1秒內能分解完畢，但人工判斷非常困難。
不過證偽（即判定它不是質數）相對容易些。雖然完全判定一個數是質數需要嘗試質因子到它的平方根，不過如果試變了100以內的質因子，依然不能除盡，那它是質數的可能性就非常大了。
對於較小的質因子，還是能迅速判別的。不過為了熟練地判斷一個大數是否有某個質因子，建議你對1000以下的數的分解質因數較為熟悉，即使不能脫口而出，最好也能在10秒內分解完畢。
以下是判斷某大數是否存在一些小質因子的方法，方法不唯一，僅供參考：
——————
2：末尾是0,2,4,6或8（這是由於2|10）
3：各位數字和是3的倍數（這是因為10^n≡1（mod 3)）
5：末位是0或5（這是由於5|10）
（以上3條法則很簡單，小學生就應該會了，3秒內可以判斷）
——————
7,11,13：考慮到1001是7,11,13的倍數，可以將一個數減去1001的整數倍，直至減到1000以下，然後口算，如306,514，迅速減去306,306，得到208，顯然它是13的倍數，所以它是13的倍數；再如699,618,115，先減去115,115得到699,503,000，再減去503,503,000，得到196,000,000，顯然它是7的倍數。
特別地，由於10^(2n)≡1（mod11),10^(2n+1)≡-1，故對於11的倍數判斷更為簡便，只要將其奇數位和偶數位各自相加，再相減即可，如6,541,216，奇數位之和為6+4+2+6=18，偶數位之和為5+1+1=7，18-7=11，所以6,541,216是11的倍數。
（以上法則也很簡單，熟練的話不超過10秒）

 
17：考慮到102是17的倍數，可以先減去17的倍數（17,34,51,68,85）把首位減到4以下，再每次減去102的倍數，如7,394,898，先前去5,100,000,得到2,294,898，再減去2,244,000，得到50,898，這個不就是51,000-102么，所以它是17的倍數。
以後的質數分解因子多數只能死算或者說即使有技巧也不太好用了，不過有些還是可以用的
——————————
37：注意到
1000≡1（mod 37），37|111
只要三位一組相加即可，如17.369.206，只要17+369+206=592，592-111*5=37,所以17.369.206是37的倍數
41：注意到 41|11111
73：注意到73|10001
等等
………………

 
其實說到底還是要靠除法能力，算得快的話2~3分鐘可以把100以內的質數都除一遍了。
此外，推薦一個網站
Wolfram|Alpha: Computational Knowledge Engine
它能迅速判斷一個大數是不是質數哦。
唉，算了~本想寫點乾貨~寫完了才知道竟然那麼水。
————————
2014.5.22 補充
對於計算機來說，對於位數很少的數來說（哪怕有10位）顯然死算就可以。

 
但是位數較多的時候（大於20位），判定一個數是否為質數的難度就很大，為此科學家創造了很多快速判定的方法，方法大多不能確保判定準確，但一般很有效，最簡單而著名的莫過於「費馬小定理」的逆命題了。
關於費馬小定理的逆命題，請移步
浼
固定基的miller rabin辦法
1，先看個位，大質數的個位必須是1，3，7，9；因為質因子有無2和5，可以一眼看出。
2，滿足上條的奇數，再觀察是否有簡單規律，比如101101之類明顯可以看出非自身質因子，可以直接排除。(如果用計算機編程，請忽略此條)。
3，大於3的奇數，可以寫成6m±1、6m±3；6m±3是3的整數倍。所以，只有6m±1可能是質數；判斷一個數是否能被3整除，各位之和是3的倍數。心算時，3的倍數計0，3連數計0，3個相同數計0，即輕易可以得出和是3的倍數的數都計0。
4，判斷有無小於20的其他質因數，7,11,13,17,19。個人計算，還是直接除吧。所謂的優秀演算法在計算機有優勢；人算時，心算和筆算都無優勢。
5，判斷有無小於n^0.5的其他質因子，如果不是質數，必然可以寫成(6m±1)(6k±1)；開根號，求得n^0.5，取出最大6m±1的m；如果6m±1不是5,7,11,13,17,19的倍數(可輕易看出的)，用6m±1去除n，看是否有餘數。
比如1389721可以寫成6m+1，[1389721^0.5]=1178=6*196+2。如果是個質數，大約再計算300多次就可以確認是否是質數。
筆算大致就是如此。
把這個數+1或者-1,能被6整除基本就是質數了,極少數的非質數也能一眼看出來,例如說35
叫哥德巴赫猜想來著..雖然還沒確實證明,但平時拿來用用足夠了.至少到現在為止四位數以內的都沒啥問題.但請不要在公開的,官方的文獻或者論文上使用,後果自負
目前為止，人們未找到一個公式可求出所有質數。
四位有的也是很簡單的，一般我不用直接除的方法去判斷是否為素數，有的數能否被13，19整除有規律，例如13|169，則13|16+4×9=52，一般地p是素數時以下x,y均為整數，
①若5能整除x＋9y,則5也能整除8x＋7y。
13的倍數問題，26，52這些都是13的倍數，而13能整除6×4+2，2×4+5，5×6-2×2，5×2-2×5，②若13能整除y+10x，則13也能整除5y-2x,13也能也整除4y+x。
③若17能整除y+10x,則17也能整除12y＋x
④若19能整除y+10x,則19也能整除2y+x
其實這樣的整除規律是很多的，而且也很好證明。
若p是素數整除ax+by,p整除ad-bc,則p整除cx+dy，其中a,b,x,y都是整數

而十近制數都輕易地寫成10k+l的形式，這是一種不同於直接看能不能整除的方法，還有方法把p的多少倍加上使得末尾是0:如果好算的話，這樣再除於10看p能不能整除這個數
  推薦閱讀：


※關於數學中實數和虛數的問題？
※為什麼0到1間的實數無法與自然數建立一一對應關係？
※如何在一個正方形畫n個相同半徑的最大的圓？
※兩個正四面體拼在一起組成的形狀算不算正六面體？
※如果有數學之神，祂會有什麼能力？
TAG:數學 | 趣味數學 | 素數 |