PythonEasyMath10 min

Check whether a number is prime

A prime is an integer greater than 1 with exactly two positive divisors. Negative numbers, zero and one are not prime. Interviewers use this problem to assess test potential factors only up to the square root.

Input

One integer n.

Output

Print true or false in lowercase.

Constraints

-10^9 <= n <= 10^9.

Example

Input

Output

true

Example 2 input

999999937

Output

true

The smallest prime needs explicit handling.

Public test cases (2)

Input
```
29
```
Expected output
```
true
```
Input
```
49
```
Expected output
```
false
```

Hints (2)

Identify the state needed to avoid repeated work.
Test potential factors only up to the square root.

Target complexity: time O(sqrt(n)) for positive n · space O(1)

Your solution

import sys


def solve_prime_check(n):
    # your code
    return False


if __name__ == "__main__":
    data = sys.stdin.read()
    n = int(data)
    result = solve_prime_check(n)
    print("true" if result else "false")

Standard input

Checking runner availability…

Reference solution

Check whether a string is a palindrome · Easy
Check whether two strings are anagrams · Easy
Compute the factorial of a number · Easy
Count vowels and consonants · Easy
Find the first occurrence with binary search · Easy
Find the missing number from zero through n · Easy
Find the second largest distinct value · Easy
Generate the Fibonacci series · Easy
Remove duplicate values while preserving order · Easy
Reverse a string · Easy

All Python programs

Check whether a number is prime

Input

Output

Constraints

Example

Public test cases (2)

Your solution

Reference solution

More Python programs