---
tags: codebook
---

{%hackmd theme-dark %}

# miller rabin

#include<iostream>
#include<vector>
using namespace std;

inline unsigned long long _pow(const long long& a,const unsigned& b,const unsigned& m){
	if(!b) return 1;
	unsigned long long tmp=_pow(a,b>>1,m);
	return (b&1?tmp*tmp%m*a%m:tmp*tmp%m);
}
bool miller_rabin(unsigned long long n){
    if(n==2) return true;
    if(n<2||!(n&1)) return false;
    unsigned u=n-1,t=0;
    while(!(u&1)) u>>=1,t++;
    vector<unsigned long long> v{2,7,61};
 	for(const auto& i:v){
 		unsigned long long a=i%n;
 		if(!a||a==1||a==n-1) continue;
 		unsigned long long x=_pow(a,u,n);
 		if(x==1||x==n-1) continue;
 		for(unsigned i=1;i<t;i++){
 			x=_pow(x,2,n);
 			if(x==1) return false;
 			if(x==n-1) break;
 		}
 		if(x==n-1) continue;
 		return false;

 	}
    return true;
}
int main(){
	size_t n;
	while(cin>>n)
		cout<<n<<(miller_rabin(n)?" is a prime!":" is not a prime.")<<endl;
	return 0;
}