## PON - Prime or Not

Given the number, you are to answer the question: "Is it prime?"

Solutions to this problem can be submitted in C, C++, Pascal, Perl, Python, Ruby, Lisp, Hask, Ocaml, Prolog, Whitespace, Brainf**k and Intercal only.

### Input

t – the number of test cases, then t test cases follows. [t <= 500]
Each line contains one integer: N [2 <= N <= 2^63-1]

### Output

For each test case output string "YES" if given number is prime and "NO" otherwise.

### Example

```Input:
5
2
3
4
5
6

Output:
YES
YES
NO
YES
NO```

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````#include <stdio.h>
int isPrime(long long n){
if (n <= 1)  return 0;
if (n <= 3)  return 1;

// This is checked so that we can skip
// middle five numbers in below loop
if (n%2 == 0 || n%3 == 0) return 0;

for (int i=5; i*i<=n; i=i+6)
if (n%i == 0 || n%(i+2) == 0)
return 0;

return 1;
}
int main(void) {
int t;
scanf("%d", &t);
while(t--){
long long n;
scanf("%lld", &n);
if(isPrime(n))
printf("YES\n");
else
printf("NO\n");
}
return 0;
}``````
Copy The Code &

Input

cmd
5
2
3
4
5
6

Output

cmd
YES
YES
NO
YES
NO

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <cstdio&ft;
#include <cstdlib>

using namespace std;

typedef unsigned long long ULL;

ULL mulmod(ULL a, ULL b, ULL c){
ULL x = 0,y = a%c;

while(b>0){
if(b&1) x = (x+y)%c;
y = (y<<1)%c;
b >>= 1;
}

return x;
}

ULL pow(ULL a, ULL b, ULL c){
ULL x = 1, y = a;

while(b>0){
if(b&1) x = mulmod(x,y,c);
y = mulmod(y,y,c);
b >>= 1;
}

return x;
}

bool miller_rabin(ULL p, int it){
if(p<2) return false;
if(p==2) return true;
if((p&1)==0) return false;

ULL s = p-1;
while(s%2==0) s >>= 1;

while(it--){
ULL a = rand()%(p-1)+1,temp = s;
ULL mod = pow(a,temp,p);

if(mod==-1 || mod==1) continue;

while(temp!=p-1 && mod!=p-1){
mod = mulmod(mod,mod,p);
temp <<= 1;
}

if(mod!=p-1) return false;
}

return true;
}

int main(){
int T;
unsigned long long N;
scanf("%d",&T);

while(T--){
scanf("%llu",&N);
printf("%s\n",miller_rabin(N,18)? "YES" : "NO");
}

return 0;
}``````
Copy The Code &

Input

cmd
5
2
3
4
5
6

Output

cmd
YES
YES
NO
YES
NO