Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- i128 mul(i128 a,i128 b,i128 m){
- i128 ans = 0;
- while(b){
- ///cout<<a<<" "<<b<<" "<<m<<endl;
- if(b&1)ans = (ans + a)%m;
- a = (a+a)%m;
- b>>=1;
- }
- return ans;
- }
- i128 power(i128 base,i128 p,i128 m){
- ///cout<<base<<" "<<p<<" "<<m<<endl;
- if(p==0)return 1;
- if(p&1)return (base % m * power(base,p-1,m) % m)%m;
- else {
- i128 x = power(base,p/2,m)%m;
- return mul(x,x,m)%m;
- }
- }
- bool miller_rabin(i128 p,i128 d){
- i128 a = rand() %(p-4) + 2;
- i128 x = power(a,d,p);
- if(x==1||x==p-1)return true;
- while(d!=p-1){
- x = mul(x,x,p)%p;
- d = d*2;
- if(x==1)return false;
- if(x==p-1)return true;
- }
- return false;
- }
- bool isPrime(i128 n){
- if(n<=1||n==4)return false;
- if(n<=3)return true;
- i128 d = n-1;
- while(d%2==0){
- d/=2;
- }
- for(int i = 0;i<4;i++)if(!miller_rabin(n,d))return false;
- return true;
- }
- int main()
- {
- //booster()
- ///read("input.txt");
- int t;
- scani(t);
- while(t--){
- ll x;
- scanf("%lld",&x);
- if(isPrime(x))puts("prime");
- else puts("composite");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement