【C++】自然数Nのk番目に小さい約数を求めるアルゴリズムを解説

問題概要

この問題では、2つの整数値 N と k が与えられ、自然数 N の k 番目に小さい約数を求めることが課題となります。

具体例を見てみましょう。

入力 : N = 15, k = 3
出力 : 5

解説 −

15 の約数は 1, 3, 5, 15
3番目に小さいのは 5

解法アプローチ①：約数を列挙してソートする方法

最もシンプルな解法は、N の約数をすべて求め、ソートした状態で保存したうえで、k 番目の値を出力することです。

手順は次のとおりです。

• 1 から √N までループし、i が N を割り切れるかどうかを判定する
• 割り切れる場合、i と N/i はペアの約数なので、両方を配列に格納する
• 配列を昇順にソートし、k 番目の要素を出力する

計算量は O(√N + D log D)(D は約数の個数)となり、十分に高速です。

実装例

上記の解法の動作を示すプログラムです。

#include <bits/stdc++.h>
using namespace std;

void findFactorK(int n, int k){
    int factors[n/2];
    int j = 0;
    // √N まで走査して約数をペアで格納
    for (int i = 1; i*i <= n; i++) {
        if (n % i == 0) {
            factors[j++] = i;
            if (i*i != n){
                factors[j++] = n / i;
            }
        }
    }
    sort(factors, factors + j);
    if (k > j)
        cout << "Doesn't Exist";
    else
        cout << factors[k-1];
}

int main(){
    int N = 16, k = 3;
    cout << k << "-th smallest divisor of the number " << N << " is ";
    findFactorK(N, k);
    return 0;
}

出力

3-th smallest divisor of the number 16 is 4

解法アプローチ②：2つのソート済み配列を使う方法

もうひとつのアプローチとして、ソートされた2つの配列を利用する方法があります。

• 1つ目の配列：√N 以下の約数 i を昇順で保存
• 2つ目の配列：対応する約数 N/i を降順で保存

この構成により、全体の約数は「1つ目の配列(昇順)+ 2つ目の配列(逆順に読むと昇順)」という順序で扱えます。したがって、

• k が 1つ目の配列のサイズ以下なら、答えは 1つ目の配列の k 番目
• それ以外なら、答えは 2つ目の配列の後ろから数えて該当する位置

として O(1) で取り出すことができ、明示的なソート処理が不要になります。

実装例

上記の解法の動作を示すプログラムです。

#include <bits/stdc++.h>
using namespace std;

void findFactorK(int n, int k){
    int factors1[n/2];  // 小さい側の約数(昇順)
    int factors2[n/2];  // 大きい側の約数(降順)
    int f1 = 0, f2 = 0;
    for (int i = 1; i*i <= n; i++) {
        if (n % i == 0) {
            factors1[f1++] = i;
            if (i*i != n){
                factors2[f2++] = n / i;
            }
        }
    }
    if (k > (f1 + f2))
        cout << "Doesn't Exist";
    else {
        if (k <= f1)
            cout << factors1[k-1];
        else
            cout << factors2[f2 - (k - f1)];
    }
}

int main(){
    int N = 16, k = 3;
    cout << k << "-th smallest divisor of the number " << N << " is ";
    findFactorK(N, k);
    return 0;
}

出力

3-th smallest divisor of the number 16 is 4

まとめ

• 約数は √N まで走査すれば「i」と「N/i」のペアとしてすべて列挙できる
• 方法①は全約数をソートして k 番目を参照する直感的な手法(O(√N + D log D))
• 方法②は小さい約数(昇順)と大きい約数(降順)を分けて管理することで、ソート不要で k 番目を求められる
• k が約数の総数を超える場合は「存在しない」として適切に処理する