ACM常用模板合集

#include<iostream> #include<algorithm> #include<cstring> #include<cstdlib> #include<cmath> #include<ctime> using namespace std; typedef long long ll; const int N = 1e5 + 7; const int times = 10; ll fast_mod(ll a,ll b,ll mod)//計算2^q的過程 {ll res = 0;while(b){if(b & 1) res = res + a;a <<= 1;if(a >= mod) a -= mod;if(res >= mod) res -= mod;b >>= 1;}return res; } ll fast_pow_mod(ll a,ll b,ll mod)//快速冪算出a^m {ll res = 1;while(b){if(b & 1) res = (res * a) % mod;a = (a * a) % mod;b >>= 1;}return res; } bool check(ll a,ll m,ll p,ll n)//對于每次隨機的a進行測試 {ll temp = fast_pow_mod(a,m,n),ret = temp;for(int i = 0;i < p;++i){ret = fast_mod(temp,temp,n);if(ret == 1 && temp != n - 1 && temp != 1) return true;temp = ret;}return ret != 1; } bool Miller_Pabin(ll n)//Miller測試的主體結構 {if(n < 2) return false;if(n == 2) return true;if(n & 1 == 0) return false;//對于偶數的優化ll p = 0,x = n - 1;//p為Miller測試的q，x為Miller測試的mwhile(x & 1 == 0){x >>= 1;p++;}srand(time(NULL));for(int i = 0;i < times;++i){ll o = rand() % (n - 1) + 1;//o就是Miller測試的底數aif(check(o,x,p,n)) return false;}return true; }int main() {ios::sync_with_stdio(false);int t;cin >> t;while(t--){long long n;cin >> n;cout << (Miller_Pabin(n) ? "Prime" : "Not a Prime") << endl;}return 0; }

總結

以上是生活随笔為你收集整理的数学--数论--Miller_Rabin判断素数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。