入門級篩素數(shù)--試除法，復雜度O（n^2）

bool rmprime( long long n ) {for(long long i = 2; i <= sqrt(n) ; i++) if(n%i == 0) return false;return true; }

?

學了一段時間算法以后，應該會了解到篩法求素數(shù)，復雜度略高于O（n）

#include<iostream> #include<cstring> using namespace std; const int MAXN = 500000; bool isp[MAXN]; int p[MAXN]; int cnt = 0;//保存素數(shù)個數(shù) void getp() {for(int i = 1; i < MAXN; i++) isp[i] = 1 ; //默認全部素數(shù)for(int i = 2; i < MAXN; i++){if(!isp[i]) continue; //如果不是素數(shù)就continue掉p[cnt++] = i;for(int j = i * 2 ; j < MX; j += i) isp[j] = 0;//記錄，往后滾處理 } }int main(){getp();for(int i = 0; i < cnt; i++) printf("%d ",p[i]);return 0; }

?當然，不難發(fā)現(xiàn)，如果MaX值過大的話，不只空間會炸，而且從頭開始掃很玄學，是不怎么可取的。

于是引入MILLER RABIN算法。可以單獨判斷一個大數(shù)是否素數(shù)，但是不保證正確。我們只能通過多次執(zhí)行算法讓這個錯誤的概率很小。//不過幸運的是，除非你是非酋王，這個算法一般都是不會出問題的。

算法的理論基礎： 1.?Fermat定理：若n是奇素數(shù)，a是任意正整數(shù)(1≤ a≤ n?1)，則 a^(n-1) ≡ 1 mod n。 2. 推演自Fermat定理（具體過程我沒看懂，Orz）,?如果n是一個奇素數(shù)，將n?1表示成2^s*r的形式，r是奇數(shù)，a與n是互素的任何隨機整數(shù)，那么a^r ≡ 1 mod n或者對某個j (0 ≤ j≤ s?1, j∈Z) 等式a^(2jr) ≡ ?1 mod n 成立。 聰明的讀者已經(jīng)發(fā)現(xiàn)上述的定理是一個數(shù)是素數(shù)的必要條件而非充分條件，所以這就是這個算法的不精確的原有，對于一些特定的檢驗算子a，存在一些合數(shù)也滿足上述定理。所以我們要多找?guī)讉€a反復檢驗，這樣能讓錯誤率大大降低。 那么我們按照上述的定理2，首先重復n次實驗。對于每一次實驗，隨機取檢驗算子a，帶入定理2進行檢驗，看看在算子a下，n能否滿足 a^r ≡ 1 mod n或者對某個j (0 ≤ j≤ s?1, j∈Z) 等式a^(2jr) ≡ ?1 mod n ? ? ? ** 如果任意一次實驗不滿足，則判定不是素數(shù)，如果都滿足，可近似可以認為是素數(shù)（錯誤率極小）。 #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <map> using namespace std;const int times = 20; int number = 0;map<long long, int>m; long long Random( long long n ) //生成[ 0 , n ]的隨機數(shù) {return ((double)rand( ) / RAND_MAX*n + 0.5); }long long q_mul( long long a, long long b, long long mod ) //快速計算 (a*b) % mod {long long ans = 0;while(b){if(b & 1){b--;ans =(ans+ a)%mod;}b /= 2;a = (a + a) % mod;}return ans; }long long q_pow( long long a, long long b, long long mod ) //快速計算 (a^b) % mod {long long ans = 1;while(b){if(b & 1){ans = q_mul( ans, a, mod );}b /= 2;a = q_mul( a, a, mod );}return ans; }bool witness( long long a, long long n )//miller_rabin算法的精華 {//用檢驗算子a來檢驗n是不是素數(shù)long long tem = n - 1;int j = 0;while(tem % 2 == 0){tem /= 2;j++;}//將n-1拆分為a^r * slong long x = q_pow( a, tem, n ); //得到a^r mod nif(x == 1 || x == n - 1) return true; //余數(shù)為1則為素數(shù)while(j--) //否則試驗條件2看是否有滿足的 j {x = q_mul( x, x, n );if(x == n - 1) return true;}return false; }bool miller_rabin( long long n ) //檢驗n是否是素數(shù) {if(n == 2)return true;if(n < 2 || n % 2 == 0)return false; //如果是2則是素數(shù)，如果<2或者是>2的偶數(shù)則不是素數(shù)for(int i = 1; i <= times; i++) //做times次隨機檢驗 {long long a = Random( n - 2 ) + 1; //得到隨機檢驗算子 aif(!witness( a, n )) //用a檢驗n是否是素數(shù)return false;}return true; }int main( ) {long long tar;while(cin >> tar){if(miller_rabin( tar )) //檢驗tar是不是素數(shù)cout << "Yes, Prime!" << endl;elsecout << "No, not prime.." << endl;}return 0; }

?

?

轉載于:https://www.cnblogs.com/shuri/p/7638588.html

總結

以上是生活随笔為你收集整理的素数判定算法 MILLER RABIN的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。