Prime Time - Practice | Unlimited Voices

Problem

Welcome to the 'Prime Time' challenge, where your mission is to become a code-breaking secret agent! In the world of espionage, messages are often encoded using prime numbers. Your task is to write a Python program to check if a given number N is prime. A prime number is greater than 1 and has no divisors other than 1 and itself. For instance, while 2, 3, 5, and 11 are prime, 4 is not because it can be divided by 2. Here's how you can crack the code: 1) Begin by understanding that any number less than 2 is not prime. 2) Check divisibility from 2 up to the square root of N, as any larger factor would have a corresponding smaller factor. 3) Return true if no divisors are found, otherwise return false. Consider edge cases like N being very small or very large, and optimize your solution to handle such scenarios efficiently.

Hints

Consider using a loop to check divisibility up to the square root of N. Think about the implications of even numbers and the efficiency of your algorithm. Edge cases include numbers like 0, 1, and very large numbers. For optimization, remember that once you find a divisor, you can conclude the number is not prime.

Input format

A single integer N (2 ≤ N ≤ 10^6) on a single line

Output format

One line containing either 'YES' if the number is prime or 'NO' if the number is not prime

Constraints

Time complexity should be less than O(N)

Sample input

Sample output

YES