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
2014-05-20 22:19:42 excursionist
TLE :(
some suggestions plz
my code is @ <snip>

Last edit: 2022-11-21 12:34:43
2014-04-07 17:48:50 [Lakshman]
@Pratyush try to learn Rabin Miller.
2014-04-07 17:24:53  .::.
got too many WA
<snip>

Last edit: 2022-11-21 12:34:37
2014-03-12 09:12:57 Anubhav Balodhi
got a tle, got too many wa.
Applying Fermat's primality test... ac 0.60 seconds, and my 95th ;-D

Last edit: 2014-03-14 04:59:22
2014-02-22 05:17:05 californiagurl
i'm getting TLE on a 21sec time limit question....facepalm.
2014-01-12 19:52:36 Martijn Muijsers
SIGPFE, sure. :P
2013-12-29 17:35:09 hiddenman
gr8 question.....
Both algo works....perfectly... :)
2013-12-29 11:55:35 Satyam Kumar Shivam
phewww finally green light :D ... even 1 iteration of fermat test worked for me.. :D ...
And 9223372036854775783 is the largest 63 bit prime.so, ans will be YES.
2013-12-27 16:05:42 Tarun Garg
@Roamn Sal dont know y but i used Miller rabin with 2 iteration and used long long unsigned everywhere still showing WA...could you pls check my submission...
2013-11-25 12:14:27 Saimadhav Heblikar
weak test cases..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.