/// Way : 1
#include<bits/stdc++.h>
#define ll unsigned long long int
using namespace std;
ll base[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
ll mod(ll a, ll b, ll m)
{
ll r = 0;
a = a%m;
while(b > 0)
{
if(b&1)
r = (r+a)%m;
b = (b >> 1); /*** b = b/2 ***/
a = (a+a)%m;
}
return r;
}
ll power(ll a, ll d, ll n)
{
ll r = 1;
a = a%n;
while(d > 0)
{
if(d&1) /*** d%2 == 1 ***/
r = mod(r, a, n);
d = (d >> 1); /*** d = d/2 ***/
a = mod(a, a, n);
}
return r;
}
bool check(ll a, ll d, ll n)
{
ll x = power(a, d, n);
if(x == 1 || x == n-1)
return true;
while(d != n-1)
{
x = mod(x, x, n);
d = (d << 1); /*** d = d * 2 ***/
if(x == 1)
return false;
if(x == n-1)
return true;
}
return false;
}
bool miller_robin(ll n)
{
ll d = n-1;
while(d%2 == 0)
d = d/2;
for(int i=0; i<25; i++)
{
if(base[i] == n)
return true;
if(check(base[i], d, n) == false)
return false;
}
return true;
}
int main()
{
ll n;
cout << "Enter Any Number :: ";
cin >> n;
if(n <= 1 || (n%2 == 0 && n != 2))
cout << n << " :: Not Prime" << "\n";
else if(n <= 3)
cout << n << " :: Prime" << "\n";
else
{
if(miller_robin(n) == true)
cout << n << " :: Prime" << "\n";
else
cout << n << " :: Not Prime" << "\n";
}
return 0;
}
Comments
Post a Comment