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

hide comments
Alexander Shlemov: 2012-08-25 21:03:47

Please, make test more strong!!! For example, add several Carmichel numbers. It's bad, when "one Fermat iteration works"

StupidGuy: 2012-08-15 13:46:18

Man..finally AC :),
Had to use 2 Iterations with Fermat's.

EDIT: Can be done with single Iteration :)

Last edit: 2012-11-18 12:05:05
Aditya Pande: 2012-07-25 03:31:01

good problem but very weak test cases and the time limit is too too high

Last edit: 2012-07-25 03:38:38
Surya kiran: 2012-06-09 07:20:50

hariprasanth Never post your code even it is WA..Your code gives YES for 35...check that

hariprasath: 2012-06-09 06:11:33

@vit YES for 9223372036854775783??

hariprasath: 2012-06-09 06:09:56

@libra not accepting,when NO for 2,3,5

Darky: 2012-03-25 05:56:37

Getting TLE even after using Little fermat th. using python! Any help?

PubLic_AvenGeR: 2012-03-06 19:08:41

Finally after 33 submissions...... :))
Python does d trick...
1 iteration f little fermat theorem..

libra: 2012-02-05 11:06:06

test cases are not proper!!i printed NO for 2,3,5 it accepted!!!

Laplace: 2012-01-22 21:21:00

GOt accepted by 1 iteration with miller rabin...algo


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