0Pricing
Coding Interview Prep · レッスン

sqrt(n) までの素数判定

1 つの数を効率よく判定します

「sqrt(n) までの素数判定」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

素数かどうかを問う

1 つの数が素数かどうかを判定することは、数学の基本的な技術です。素数には、1 とその数自身というちょうど 2 つの約数があります。高速に判定してみましょう。🔍

素朴な判定

2 から n - 1 までのすべての数で n を割ってみることもできます。正しい方法ですが、n が大きいと非常に遅くなります。

平方根の工夫

ここで重要な着眼点があります。調べる必要があるのは、n の平方根以下の約数だけです。それより大きい範囲に新しい因数が現れることはありません。

平方根までで十分な理由

約数は、積が n になる組で現れます。両方が平方根より大きいと、その積は n を超えてしまいますが、これは不可能です。

ループの上限

i*i が n 以下である間、i を 2 から増やしていきます。i*i を使えば、大きな整数で sqrt を使う際の浮動小数点誤差を避けられます。

while i * i <= n:
    ...

小さい値を扱う

2 未満の数は素数ではないため、最初に除外します。このガードによって、メインループを簡潔かつ正しく保てます。

if n < 2:
    return False

関数全体

すべてを組み合わせます。小さい値をガードしてから、平方根までの約数候補を調べます。余りなく割り切れれば、n は合成数です。

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

高速化する

2 は個別に確認し、その後は奇数だけを調べます。偶数を飛ばすだけで、複雑さを増やさずに処理量をおよそ半分にできます。

if n % 2 == 0:
    return n == 2

計算量

この判定の計算量は O(sqrt n) です。10 億以下の 1 つの数なら、必要なのは約 30,000 回の軽い操作だけです。

1 つの数を調べる場合

平方根まで調べる方法は、1 回または少数の問い合わせで効果を発揮します。範囲全体の素数性を判定する必要があるなら、ふるいの方がはるかに高速です。

平方根の落とし穴を避ける

math.sqrt ではなく i*i と比較すれば、境界付近の数を誤って素数と判定したり、素数でないと判定したりする丸め誤差を避けられます。

確認

この判定を高速にする上限を確認します。

まとめ

これで、1 つの数の素数性を O(sqrt n) 時間で判定し、小さい値をガードし、偶数を飛ばし、正確さを保つために i*i を使えるようになりました。✅

よくある質問

「sqrt(n) までの素数判定」レッスンは無料ですか？

はい。「sqrt(n) までの素数判定」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「sqrt(n) までの素数判定」で何を学びますか？

1 つの数を効率よく判定します ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。

「sqrt(n) までの素数判定」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. GCD、LCM、ユークリッドの互除法
  2. sqrt(n) までの素数判定
  3. エラトステネスのふるい
  4. 素因数分解と約数
← Coding Interview Prepに戻る