หา Good Number มากที่สุดใน Divisors ของ N ใน C++

ในปัญหานี้ เราได้รับตัวเลข N งานคือหา Good Number มากที่สุดในตัวหารของ N

Good Number คืออะไร?

ตัวเลขที่ทุกหลักมีค่า มากกว่า ผลรวมของหลักทางขวาทั้งหมด

ตัวอย่าง: 732 เป็น Good Number เพราะ 7 > 3+2 และ 3 > 2

ตัวอย่าง

Input: N = 15 Output: 15

Divisors of 15: 1, 3, 5, 15 → 15 เป็น good number มากที่สุด

ข้อสังเกตสำคัญ

Good number มากที่สุดใน divisors จะเป็น ผลคูณของตัวประกอบเฉพาะที่ไม่ซ้ำกันทั้งหมดของ N (Square-free kernel)

ตัวอย่างโค้ด

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

int findLargestGoodNumber(int n) {
    vector 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() {
    cout << findLargestGoodNumber(28); // 2 * 7 = 14
    return 0;
}

ผลลัพธ์

14

(Divisors of 28: 1, 2, 4, 7, 14, 28 → Good numbers: 1, 2, 7, 14 → มากที่สุดคือ 14)