Efficient Prime Checker

You are given an integer n. Your task is to determine whether n is a prime number.

A prime number is defined as a natural number greater than 1 that has no positive divisors other than 1 and itself. In mathematical terms, a number \(n > 1\) is prime if for every integer \(d\) such that \(2 \le d \le \sqrt{n}\), \(d\) does not divide \(n\) evenly.

Your solution should implement an efficient algorithm that only iterates up to \(\sqrt{n}\) to determine the primality. The program will read the input from stdin and output the result to stdout.

inputFormat

The input consists of a single integer (n) provided via standard input (stdin).

outputFormat

Output a single line to standard output (stdout) containing True if (n) is a prime number, or False otherwise.## sample

2

True