Prime Number Checker

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

A prime number is defined as a natural number greater than 1 that has no positive divisors other than 1 and itself. In other words, if n is prime, you should output Prime; otherwise, output Not prime.

The problem can be mathematically formulated as follows:

Determine if \[ n \text{ is prime} \iff \begin{cases} n > 1 & \text{and} \\ \forall d \in \mathbb{Z},\, 2 \le d \le \lfloor\sqrt{n}\rfloor: d \nmid n \end{cases} \]

inputFormat

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

outputFormat

Output a single string: Prime if n is a prime number, or Not prime otherwise. The output should be written to stdout.

29

Prime