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

Added by:Roman Sol
Date:2005-01-24
Time limit:21s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ADA95 ASM32 BASH CSHARP CLPS D ERL FORTRAN ICON JAVA JS-RHINO LUA NEM NICE PHP PIKE ST
Resource:ZCon 2005

hide comments
2013-05-04 12:34:57 ওয়াসী (Wasi)
AC at 1st submission with Miller_Rabin algo...:D
Nice problem!
2013-05-04 11:41:51 Ouditchya Sinha
Nice problem, Learnt Non-deterministic primality testing algos. AC in 0.16s :)
2013-04-13 06:22:35 mystique_blue
So far this is the problem that gave me most number of WA's, and also made me learn a number of amazing algos.

I like this category of problems.

Last edit: 2013-04-13 06:23:19
2013-03-13 06:11:35 Alien
GOT AC in 0.13 SEC, whereas time-limit is 21 sec
2013-01-22 07:20:18 shreyash pandey
python nails this question :)
2012-12-28 08:09:28 gourav
just hats off to this qstn!! if one has done this qstn, he can play with any prime number afterwards.. just one thing changed in my first code for this qstn.. got AC !! haha.. :-)

Last edit: 2012-12-28 08:09:44
2012-12-23 18:55:56 god_father
really very good question learn a lot....
need 2 iterations of little fermit theorm.
2012-12-21 01:48:32 Akb
got AC in 0.22 sec, Time Limit is 21 sec...!! :D
2012-12-09 09:27:35 Erik Lonèarek
@himanshu sahu - TLE stands for Time Limit Exceeded, which means your program is too slow for this problem. Limit is 21 seconds but test cases are very very large.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.