Prime Number Check

Given an integer n, determine whether it is a prime number. A prime number is an integer greater than 1 that has no positive divisors other than 1 and itself. Print "YES" if n is prime, and "NO" otherwise.

Input: A single line containing one integer n. Output: Print "YES" if n is prime, otherwise print "NO".

1 <= n <= 10^12

Special-casing 2 (checking it separately) and then only testing ODD numbers afterward is a small but meaningful optimization - it immediately skips half of all possible divisors without any risk of missing a genuine one.

Check whether a number is prime - divisible only by 1 and itself. Brute force: Check every integer from 2 up to n-1 as a potential divisor - this costs O(n), far more than necessary for large n (up to 10^12 here). Optimised: If n has a divisor GREATER than sqrt(n), it must also have a corresponding divisor SMALLER than sqrt(n) (since divisors pair up around the square root) - so checking only up to sqrt(n) is guaranteed to find a divisor if one exists, cutting the work from O(n) down to O(sqrt(n)).

1. Numbers less than 2 are never prime - handle this immediately. 2. You only need to check for divisors up to sqrt(n) - if none divide n, it's prime. 3. Handle 2 separately (the only even prime), then only test ODD divisors afterward, roughly halving the work for large n.

Time: O(sqrt(n)) - checking divisors only up to the square root of n. Space: O(1) - just a loop counter.

n=1 is not prime. Even numbers greater than 2 can be rejected in O(1) before entering the sqrt(n) loop. n can be as large as 10^12, so use a 64-bit type and loop up to sqrt(n) (about 10^6 iterations).

Be ready to explain WHY checking only up to sqrt(n) is sufficient - the 'divisors pair up around the square root' argument is the entire justification, and articulating it clearly is often exactly what's being tested.