Tìm số từ các ước số của nó trong C++

Giới thiệu

Cho mảng divisors[] chứa các ước số của một số Num (không bao gồm 1 và chính nó). Tìm Num.

Ví dụ minh họa

Đầu vào

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

Đầu ra

75

Giải thích

Số 75 có các ước (trừ 1 và 75): {3, 5, 15, 25}

Phương pháp giải

Số Num = ước nhỏ nhất × ước lớn nhất. Sắp xếp mảng ước, nhân phần tử đầu và cuối. Sau đó kiểm tra: tìm tất cả ước của Num (trừ 1 và Num), so sánh với mảng cho trước. Nếu khớp thì trả về Num, ngược lại trả về -1.

Chương trình minh họa

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

int findNumberFromDiv(int divisors[], int n) {
    sort(divisors, divisors + n);
    int num = divisors[0] * divisors[n - 1];
    
    vector numDiv;
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            numDiv.push_back(i);
            if (i != num / i)
                numDiv.push_back(num / i);
        }
    }
    sort(numDiv.begin(), numDiv.end());
    
    if (numDiv.size() != n) return -1;
    for (int i = 0; i < n; 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;
}

Đầu ra

The number is 75