A student's program needs to check primality of large numbers efficiently for a cryptography demo Farhan is preparing. Read an integer N. Print "PRIME" or "NOT PRIME". Your check must run in O(sqrt(N)), not O(N).
Input
One integer N.
Output
"PRIME" or "NOT PRIME".
Constraints
2 ≤ N ≤ 10^12
Sample Input
97
Sample Output
PRIME
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.