Pythonでnのk番目の約数を求めるプログラムの作成方法

正の整数 n と k が与えられたとします。n のすべての約数を昇順に並べたリストを考え、その中から k 番目の約数を求めます。もし約数の個数が k 個未満であれば、-1 を返します。

たとえば、入力が n = 28、k = 4 のとき、出力は 7 になります。28 の約数は [1, 2, 4, 7, 14, 28] であり、その 4 番目が 7 だからです。

解法のアプローチ

この問題は、次の手順で解くことができます。

• k が 1 の場合は、最小の約数が必ず 1 であるため、1 を返します。
• cand を「1」のみを含むリストとして初期化します。
• i を 2 から ⌊√n⌋ まで順に調べ、n が i で割り切れる場合は i を cand の末尾に追加します。
• m を cand の要素数とします。
• k > 2×m の場合、または k = 2×m かつ n が cand の最後の要素の 2 乗に等しい場合、約数が k 個存在しないため -1 を返します。
• k ≤ m の場合は、小さい側の約数に該当するため cand[k-1] を返します。
• それ以外の場合は大きい側の約数に該当します。factor を cand[2×m − k] とし、n ÷ factor の商を返します。

このアルゴリズムのポイントは、約数が「i と n/i」というペアで現れるという性質を利用している点です。√n までの小さい約数だけを列挙すれば、対応するペアから大きい約数を導き出せるため、計算量を O(√n) に抑えることができます。

実装例(Python)

以下の実装例を見ると、より理解しやすくなります。

from math import floor

def solve(n, k):
    if k == 1:
        return 1
    cand = [1]
    for i in range(2, 1 + floor(pow(n, 0.5))):
        if n % i == 0:
            cand.append(i)
        m = len(cand)
        if k > 2 * m or (k == 2 * m and n == cand[-1] ** 2):
            return -1
        if k <= m:
            return cand[k - 1]
        factor = cand[2 * m - k]
        return n // factor

n = 28
k = 4
print(solve(n, k))

入力

28, 4

出力

7