素数判定

問題

素数とは、1より大きく、1と自分自身以外に約数を持たない数です。約数のチェックは n の平方根までで十分です。

is_prime(n) を実装してください。

n: 判定する数。

n が素数なら true、そうでなければ 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 は 1 と 29 以外に約数がありません。

例 2

入力：
n = 21

期待される出力：
expected = False

入力：
long long n = 21;

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

入力：
long n = 21;

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

21 = 3 × 7 なので、素数ではありません。

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

ヒント 1

2未満は先に処理する。素数ではない。

ヒント 2

割り切れるかは平方根まで調べれば十分。

ヒント 3

偶数や重複する因子に注意。1つでも割り切れれば素数ではない。

目安の計算量

時間 O(sqrt(n))、追加メモリ O(1)

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