#include <iostream>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;
// big numbers
long mulmod(long a, long b, long MOD){
if (b == 0) return 0;
long res = mulmod(a, b >> 1, MOD);
res += res;
res %= MOD;
return (b & 1)? (a + res) % MOD : res;
}
bool witness(long a, long n) {
long d = 1;
long b = n - 1;
for(int i = 63; i >= 0; i--){
if(b < pow(2.0, i)) continue;
long x = d;
d = mulmod(d, d, n);
if (d == 1 && x != 1 && x != n - 1) return true;
if ((b >> i) & 1) d = mulmod(d, a, n);
}
return (d != 1);
}
bool MillerRabin(long n, long tries) {
for(int it = 0; it < tries; it++) {
if(witness(rand() % (n - 1) + 1, n))
return false;
}
return true;
}
// low numbers
#define forn(i, n) for(int i = 0; i < int(n); i++)
bool witnessLow(int a, int n) {
int d = 1;
int b = n - 1;
for(int i = 31; i >= 0; i--) {
if(b < (1 << i)) continue;
int x = d;
d = (long(d) * d) % n;
if(d == 1 && x != 1 && x != n - 1) return true;
if((b >> i) & 1) d = (long(d) * a) % n;
}
return (d != 1);
}
bool MillerRabinLow(int n) {
if(n == 2) return true;
if(witnessLow(2, n)) return false;
return true;
}
bool test(long c){
if (c < 1e9)
return MillerRabinLow(c);
else
return MillerRabin(c, 19);
}
int main()
{
int arr[] = {2047, 3277};
for(int i = 0; i < 2; i++)
{
cout<<arr[i]<<" - ";
if(test(arr[i]))
cout<<"SIMPLE"<<endl;
else
cout<<"NOT SIMPLE"<<endl;
}
return 0;
}