Check Prime Number
素数とは、1より大きい整数で、約数が1とその数自身だけである数です。正の整数nが与えられます。nが素数ならtrueを、そうでなければfalseを返してください。1は素数ではありません。
関数
- ninteger
- テストする正の整数
- 戻り値boolean
- nが素数ならtrue、そうでなければfalse
制約
1 ≤ n ≤ 231 - 1
例
- 入力
- n = 29
- 出力
- true
- 説明
2、3、4、5のいずれも29を割り切らず、6 × 6 = 36はすでに29を超えているため、これ以上探す約数はありません。29は素数です。
- 入力
- n = 1
- 出力
- false
- 説明
- 素数は約数をちょうど2つ持ちます。
1とそれ自身です。1は約数を1つしか持たないため、答えはfalseです。
- 入力
- n = 91
- 出力
- false
- 説明
91は素数に見えますが、7 × 13 = 91です。探索が√91 ≈ 9.5を過ぎる前に、約数7が見つかります。
提出時に隠しテスト+15件
発展問題
3 より大きいすべての素数は、6k-1 または 6k+1 の形をしています。この性質を使って、候補となる約数の3分の1だけをテストできますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
素数には、
2とn-1の間に約数がありません。その範囲全体を本当に調べる必要がありますか？dがnを割り切るなら、n / dもnを割り切り、この2つのうち一方は√n以下です。d * dがnを超えたら終了できます。- まず、
n < 2と2以外の偶数を除外します。次に、d * d ≤ nの間、3から奇数の約数を調べ、d * dは64ビット型で保持します。
解説
定義では、2からn-1までのすべての約数を除外するとされていますが、最大の素数を入力した場合、割り算の回数は20億回を超えます。約数は、積がnになるペアを作り、それぞれのペアの小さい方は√n以下です。したがって、√nまで調べれば十分で、奇数の候補は最大でも約23,000個です。
すべての約数を試す
正しいが、最大のテストでは終わらない
考え方
定義からアルゴリズムが導けます。数 n ≥ 2 が素数であるのは、2, 3, ..., n-1 のどれもそれを割り切らない場合です。各候補 d について n % d == 0 をテストし、割り切れるものが見つかった時点で false を返します。91 の場合、ループは 2 から 6 まで試し、7 で停止します。
まず n < 2 を処理します。n = 1 の場合、候補の範囲は空なので、ループは約数を見つけられず、1 を素数と判定してしまいます。
合成数は通常早い段階で停止しますが、素数はすべてのテストを通過するため、ループは最後まで実行されます。素数である n = 2147483647 の場合、約 2.1 × 10^9 回の除算が必要になり、数秒で処理するには多すぎます。
アルゴリズム
n < 2の場合、falseを返します。2からn-1までdをループします。n % d == 0の場合、falseを返します。- ループの後、
trueを返します。
def isPrime(n):
if n < 2:
return False
for d in range(2, n):
if n % d == 0:
return False
return True平方根までの試し割り
考え方
約数はペアになります。d が n を割り切るなら、n / d も n を割り切り、この2つを掛けると n になります。積が n より大きくなってしまうため、両方が √n より大きくなることはありません。したがって、n に 1 とそれ自身以外の約数があるなら、√n 以下の約数があります。91 の場合、そのペアは 7 と 13 で、7 ≤ 9.5 です。√n 以下の数で n を割り切れるものがなければ、それより大きい数にもありません。
平方根関数を呼び出す代わりに、上限を d * d ≤ n と書きます。整数のまま処理でき、丸めもありません。等号が重要です。49 = 7 × 7 であり、その約数 7 はちょうど √49 の位置にあります。
候補を半分に減らすこともできます。2 は個別に扱います。偶数の n が素数になるのは、2 の場合だけです。それ以降は、奇数の n の約数も奇数だけなので、3 から始めて 2 ずつ増やします。n = 2147483647 の場合、ループの実行回数は約 2.1 × 10^9 回ではなく、約 23,000 回になります。
アルゴリズム
n < 2の場合は、falseを返します。nが偶数の場合は、n == 2かどうかを返します。dを3から始め、d * d ≤ nの間ループします。dには64ビット型を使用します。n % d == 0の場合は、falseを返します。そうでなければ、dに2を加えます。- ループの後、
trueを返します。
def isPrime(n):
if n < 2:
return False
if n % 2 == 0:
return n == 2 # 2 is the only even prime
d = 3
while d * d <= n:
if n % d == 0:
return False
d += 2
return True
落とし穴と境界ケース
考え方は一行で説明できます。バグは境界、つまり最小の入力値と最後の約数で発生します。
1に対してtrueを返す。約数は2つではなく1つなので、素数ではありません。- 偶数だからという理由で
2を除外する。偶数を除外する前にn == 2を確認してください。 ≤ではなくd * d < nの間ループする。すると、9、49、2147117569 = 46337²のような素数の平方が素数として扱われます。d * dでオーバーフローする。32ビットのintでは、46341 × 46341 = 2147488281は収まらず、負の数に折り返されるため、判定を通過し続け、ループが√nを大きく超えて実行されます。dに64ビット型を使うか、代わりにd ≤ n / dと比較してください。- 浮動小数点の
sqrtから上限を求めて切り捨てる。この場合、すべてのnに対してdoubleは正確ですが、64ビットの入力では丸めによって真の平方根より1小さい値になり、重要な約数を1つ見落とすことがあります。d * d ≤ nにはそのようなリスクはありません。
よくある質問4
数が素数かどうかを確認する時間計算量はどれくらいですか？
√nまで試し割りを行うと、時間計算量はO(√n)、空間計算量はO(1)です。nが2^31-1までの場合、割り算の回数は最大で約46,000回、偶数の除数を省けば23,000回です。n-1までのすべての除数を試す方法はO(n)で、最大の入力では約20億ステップになります。
なぜ n の平方根までの約数だけを調べるのですか？
約数は、積が n になる d と n / d のペアになります。両方が √n より大きければ、その積は n より大きくなります。したがって、各ペアには √n 以下の要素があり、そこまでに約数が見つからなければ、n は素数です。
1は素数ですか？
いいえ。素数は異なる約数をちょうど2つ持ちます。1とその数自身です。一方、1の約数は1つだけです。1を除外することで、すべての整数の素因数分解が一意になります。そのため、isPrime(1)はfalseを返します。
非常に大きな数が素数かどうかを、もっと速く判定する方法はありますか？
32 ビットの数値 1 つなら、√n までの試し割りで十分高速です。数十桁の数値には、約数を試す代わりにいくつかの剰余べき乗を調べるミラー–ラビン素数判定法を使います。上限までのすべての素数を列挙するには、個々の数を検査するよりエラトステネスのふるいのほうが効率的です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def isPrime(n):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
n = 29
期待値
true