Pythonで与えられた数の素因数をすべて効率的に出力するプログラムの作成方法

本記事では、与えられた整数の素因数（そいんすう）をすべて効率的に求めて出力するPythonプログラムについて詳しく解説します。

問題文

ある整数 n が与えられたとき、その数を構成するすべての素因数を見つけて出力することです。
例えば 200 の場合、200 = 2 × 2 × 2 × 5 × 5 と分解できるため、出力は「2, 2, 2, 5, 5」となります。

効率的なアプローチとは

2からnまですべての数で割り切れるかを順番に確認する素朴な方法では、計算量が O(n) かかり非効率です。そこで、次の3つの性質を利用することで、計算量を O(√n) まで削減できます。

• まず2で割れるだけ割る … 偶数の素因数をすべて取り除き、n を奇数にします。
• 3以上の奇数で√nまで試し割りする … 合成数の素因数は必ず√n以下に存在するため、それ以降を調べる必要はありません。
• 最後に残った数が2より大きければ、それ自体が素因数 … 残った数は必ず素数であることが保証されます。

サンプルコード

# Python program to print prime factors
import math

def primeFactors(n):
    # 2で割り切れる間は2を出力して割る
    while n % 2 == 0:
        print(2)
        n = n // 2
    # nは奇数になったので、3から√nまでの奇数で試し割り
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        # iで割り切れる間はiを出力して割る
        while n % i == 0:
            print(i)
            n = n // i
    # 最後に残った数が2より大きければ、それ自体が素因数
    if n > 2:
        print(n)

n = 200
primeFactors(n)

実行結果

2
2
2
5
5

上図のように、変数や関数はすべてグローバルスコープで宣言されています。

コードのポイント

• 除算には //（整数除算）を使用することで、結果が浮動小数点数になるのを防ぎ、正しく動作します。
• range(3, int(math.sqrt(n)) + 1, 2) により、3, 5, 7, … と奇数のみを効率よくチェックできます。
• 同じ素因数が複数回現れる場合（例：200 の「2」が3回）も、内側の while ループですべて出力されます。

まとめ

本記事では、Pythonを使って与えられた整数の素因数をすべて効率的に出力する方法を学びました。「2で割り切れる間は割り続ける」「その後は√nまでの奇数だけで試し割りする」という工夫により、計算量を O(n) から O(√n) に大幅に削減でき、大きな数でも高速に素因数分解が可能になります。素因数分解は暗号技術や競技プログラミングなどでも応用される基本的なアルゴリズムなので、ぜひマスターしておきましょう。