【Python】ある数の最大の素因数を求めるプログラムの書き方

この記事では、「与えられた整数の最大の素因数を求める」という問題に対する解決方法を、具体的なコード例とともにわかりやすく解説します。

問題文

正の整数 n が与えられたとき、その数の最大の素因数を求めます。

例えば n = 15 の場合、15 は 3 × 5 と素因数分解できるため、答えは 5 となります。

解き方のアプローチ

• 入力された数を、小さい約数から順番に割っていくことで素因数分解します。
• 割り切れるたびに、その時点での約数（素因数）を「最大値」として更新していきます。
• 平方根まで調べれば十分なため、計算量を抑えられます。

実装例（サンプルコード）

import math

def maxPrimeFactor(n):
    max_Prime = -1

    # まず偶数（2）で割り切れるだけ割る
    while n % 2 == 0:
        max_Prime = 2
        n //= 2

    # 残った奇数について、3から√nまで調べる
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        while n % i == 0:
            max_Prime = i
            n //= i

    # 2より大きい素数が残っていれば、それが最大の素因数
    if n > 2:
        max_Prime = n

    return int(max_Prime)

# 上記の関数をテストするドライバーコード
n = 15
print(maxPrimeFactor(n))

コードのポイント

このアルゴリズムでは、まず 2 で割り切れる限り割り続けることで偶数の要素を取り除きます。その後、3 から始めて 2 ずつ増やしながら奇数のみを確認することで、無駄な計算を省いています。最後に 2 より大きい数が残った場合、それはそれ自体が素数であることを意味するため、そのまま最大の素因数として返します。

計算量

時間計算量： O(n^1/2)（平方根オーダー）

補助空間： O(1)（追加のメモリは不要）

出力結果

5

15 を素因数分解すると 3 × 5 となるため、最大の素因数である 5 が出力されます。

まとめ

この記事では、Python を使ってある数の最大の素因数を効率的に求める方法を学びました。試し割り法の基本的な考え方を応用すれば、大きな数でも O(√n) の計算量で高速に処理できます。素因数分解は暗号技術などにも応用される重要な概念なので、ぜひ理解を深めてください。