[模板] Miller-Rabin 素数测试
发布时间:2020-12-14 03:22:43 所属栏目:大数据 来源:网络整理
导读:细节挺多的。。 #includeiostream #include cstdlib #include cstdio #include ctime using namespace std;typedef long long ll;ll mul(ll a,ll b,ll mod) { ll ret = 0ll; a %= mod; while ( b ) { if ( b 1ll ) ret = ( ret + a ) % mod,b-- ; b = 1ll; a
细节挺多的。。 #include<iostream> #include<cstdlib> #include<cstdio> #include<ctime> using namespace std; typedef long long ll; ll mul(ll a,ll b,ll mod) { ll ret = 0ll; a %= mod; while( b ) { if ( b & 1ll ) ret = ( ret + a ) % mod,b--; b >>= 1ll; a = ( a + a ) % mod; } return ret; } ll qpow(ll a,ll mod) { ll ret = 1ll; a %= mod; while( b ) { if ( b & 1ll ) ret = mul(ret,a,mod),b--; b >>= 1ll; a = mul(a,mod); } return ret; } ll ter[15]= {0,2,3,5,7,11,13,17,19,23,29}; const int TOP=10; bool Miller_Rabin(ll n) { if ( n==2ll||n==3ll ) return true; if ( !( n & 1ll ) ) return false; ll d = n - 1ll; int s = 0; while( !( d & 1ll ) ) ++s,d>>=1ll; for(int i=1; i<=TOP; i++) { ll a = ter[i]; if(a>=n) return true; ll x = qpow(a,d,n); ll y = 0ll; for(int j=0; j<s; j++) { y = mul(x,x,n); if ( 1ll == y && 1ll != x && n-1ll != x ) return false; x = y; } if ( 1ll != y ) return false; } return true; } int main() { ll x; while(cin>>x) { Miller_Rabin(x)?cout<<"YESn":cout<<"NOn"; } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |