Prime Number Checker

Given an integer \(n\), determine whether it is a prime number. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. In mathematical terms, an integer \(n\) is prime if and only if \(n > 1\) and for every integer \(a\) such that \(2 \leq a \leq \sqrt{n}\), \(a\) does not divide \(n\).

Your task is to implement a function that checks this property efficiently.

inputFormat

The input consists of a single line containing an integer \(n\) (\(1 \leq n \leq 10^9\)).

outputFormat

Output a single line: True if \(n\) is a prime number, otherwise False.

2

True