Tìm số Good lớn nhất trong các ước của N trong C++

Cho số N. Nhiệm vụ: tìm số Good lớn nhất trong các ước của N. Số Good: mọi chữ số đều lớn hơn tổng các chữ số bên phải nó (ví dụ 732: 7>3+2, 3>2).

Ví dụ minh họa

Input: N = 15 Output: 15

Ước của 15: 1, 3, 5, 15. Số Good lớn nhất là 15.

Phương pháp giải

Số Good lớn nhất trong các ước là tích của tất cả thừa số nguyên tố phân biệt của N.

Ví dụ chương trình

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

int findLargestGoodNumber(int n){
    vector<int> primeFactors;
    int x = n;
    for (int i = 2; i * i <= n; i++) {
        if (x % i == 0) {
            primeFactors.push_back(i);
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) primeFactors.push_back(x);
    int goodNumber = 1;
    for (int p : primeFactors) goodNumber *= p;
    return goodNumber;
}

int main(){
    int n = 28;
    cout << "Số Good lớn nhất trong ước của " << n << " là " << findLargestGoodNumber(n);
    return 0;
}

Kết quả

Số Good lớn nhất trong ước của 28 là 14