Prime Number Check

問題

A prime number is greater than 1 and divisible only by 1 and itself. Checking divisors up to the square root of n is enough.

Implement is_prime(n).

n: The number to test.

Return true if n is prime, otherwise false.

-1,000 ≤ n ≤ 1,000,000,000,000

例 1

入力：
n = 29

期待される出力：
expected = True

入力：
long long n = 29;

期待される出力：
bool expected = true;

入力：
long n = 29;

期待される出力：
bool expected = true;

29 has no divisors other than 1 and 29.

例 2

入力：
n = 21

期待される出力：
expected = False

入力：
long long n = 21;

期待される出力：
bool expected = false;

入力：
long n = 21;

期待される出力：
bool expected = false;

21 = 3 × 7, so it is not prime.

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

Handle numbers below 2 first; they cannot be prime.

ヒント 2

Test possible divisors only up to the square root of the number.

ヒント 3

Watch out for even numbers and repeated factors, since one divisor is enough to disqualify primality.

目安の計算量

O(sqrt(n)) time, O(1) extra space

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。