素因数分解と約数
N を素数の累乗に分解し、約数の個数を数えます
「素因数分解と約数」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
N を分解する
1 より大きいすべての整数は、素数の積として一意に表せます。その分解である素因数分解を求めると、数論の多くの問題を解けるようになります。🧩
試し割りの考え方
n を割り切る最小の素数を取り出し、その素数で割ってから繰り返します。この単純な試し割りによって、n を 1 まで小さくしていきます。
平方根までループする
i*i が n 以下である間、約数 i を調べます。平方根を超えると、残る素因数は多くても 1 つです。
while i * i <= n:
...各因数を取り出す
i が n を割り切る間、割り続けて i を記録します。これにより、次へ進む前にその素数のべきをすべて取り出せます。
while n % i == 0:
factors.append(i)
n //= i残った素数
ループの後も n が 1 より大きければ、それ自体が平方根より大きい素数因数です。1 回だけ追加します。
if n > 1:
factors.append(n)処理全体
これらを組み合わせると、計算量 O(sqrt n) で素因数分解できます。各素数を重複度も含めて、順番にすべて返します。
def factorize(n):
f, i = [], 2
while i * i <= n:
while n % i == 0:
f.append(i); n //= i
i += 1
if n > 1: f.append(n)
return fべきごとにまとめる
約数の個数を数えるには、2,2,2 ではなく 2^3 のように、各素数とその指数が必要です。Counter を使えば重複を簡潔に集計できます。
from collections import Counter
exp = Counter(factorize(n))約数の公式
n が p1^a × p2^b なら、約数の個数は (a+1) × (b+1) です。各指数には 1 つ余分な選択肢があるためです。
約数の個数
すべての素数について指数に1を足し、それらを掛け合わせます。これで約数を列挙しなくても、約数の個数を求められます。
count = 1
for e in exp.values():
count *= (e + 1)約数の総和
関連する公式では、各素数の等比級数を使って約数の総和を求めます。これを知っておくと、完全数やアリコート問題に役立ちます。
ふるいで高速化
多数の数を素因数分解する場合は、ふるいを使って各数の最小素因数をあらかじめ計算しておきます。すると、各クエリを O(log n) ステップで素因数分解できます。
確認問題
具体的な数に約数の個数を求める公式を適用してみましょう。
まとめ
これで、試し割りによって O(sqrt n) で N を素因数分解し、残った素数を処理し、指数をまとめ、積の公式で約数の個数を求められるようになりました。✅
よくある質問
「素因数分解と約数」レッスンは無料ですか？
はい。「素因数分解と約数」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「素因数分解と約数」で何を学びますか？
N を素数の累乗に分解し、約数の個数を数えます ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「素因数分解と約数」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。