C++で約数の配列から元の数を求める方法

この問題では、ある数 Num の約数からなる N 個の整数の配列 divisors[] が与えられ、その約数のリストから元の数を特定することが課題となります。

なお、約数の配列には 1 とその数自身は含まれません。

具体例で問題を確認しましょう。

入力

divisors[] = {3, 25, 5, 15}

出力

75

説明

数 75 の約数は {3, 25, 5, 15} です

解法のアプローチ

この問題を解く鍵となるのは、数の最小の約数と最大の約数を組み合わせることです。元の数 Num は次の式で求められます。

Num = 最小の約数 × 最大の約数

そのため、まず配列 divisors[] を昇順にソートし、先頭と末尾の要素の積を計算します。

次に、求めた候補の数 Num についてすべての約数を列挙し、それらが与えられた約数の配列と完全に一致するかどうかを検証します。一致していれば Num を返し、一致しない場合は -1 を返します(これは元の数が存在しないことを示します)。

解法の動作を示すプログラムは以下の通りです。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int findNumberFromDiv(int divisors[], int n){
    sort(divisors, divisors + n);
    int num = divisors[0] * divisors[n - 1];
    int numDiv[2*n];
    int count = 0;
    for (int i = 2; i * i <= num; i++){
        if (num % i == 0){
            numDiv[count] = i;
            count ++ ;
            numDiv[count] = num/i;
            count++;
        }
    }
    sort(numDiv, numDiv + count);
    if (count != n)
        return -1;
    else{
        for (int i = 0; i < count; i++) {
            if (divisors[i] != numDiv[i])
                return -1;
        }
    }
    return num;
}
int main(){
    int divisors[] = { 3, 25, 5, 15 };
    int n = sizeof(divisors) / sizeof(divisors[0]);
    cout<<"The number is "<<findNumberFromDiv(divisors,n);
    return 0;
}

出力

The number is 75