Four Divisors ใน C++ : หาผลรวมตัวหารของจำนวนที่มีตัวหาร 4 ตัว

ให้ Array nums หา **ผลรวมของตัวหารทั้งหมด** ของจำนวนใน Array ที่มี **ตัวหารทั้งหมด 4 ตัว** (พอดี) ถ้าไม่มีจำนวนไหน -> Return 0

ตัวอย่าง

nums = [21, 4, 7]

• 21: ตัวหาร {1, 3, 7, 21} -> **4 ตัว** -> Sum = 32
• 4: ตัวหาร {1, 2, 4} -> 3 ตัว
• 7: ตัวหาร {1, 7} -> 2 ตัว

Output: 32 (Sum ของตัวหาร 21 เท่านั้น)

แนวทาง: Factorization + Counting Divisors

สำหรับแต่ละ x ใน Array:

1. Initialize sum = 1 + x, count = 2 (1 และ x เอง)
2. Loop i = 2 .. sqrt(x):
   • ถ้า x % i == 0:
     • sum += i, count++
     • ถ้า i != x/i -> sum += x/i, count++
3. ถ้า count == 4 -> Return sum, Else Return 0

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

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

class Solution {
public:
    int sumOfDivisorsIfFour(int x) {
        int sum = 1 + x;
        int cnt = 2;
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) {
                sum += i;
                cnt++;
                if (i != x / i) {
                    sum += x / i;
                    cnt++;
                }
            }
        }
        return (cnt == 4) ? sum : 0;
    }

    int sumFourDivisors(vector<int>& nums) {
        int ret = 0;
        for (int x : nums) ret += sumOfDivisorsIfFour(x);
        return ret;
    }
};

Input / Output

Input:  [21,4,7]
Output: 32

ความซับซ้อน (Complexity)

• Time: O(N * √M) — N = |nums|, M = max(nums[i]) (Factorization ต่อจำนวน)
• Space: O(1)

Optimization (ถ้า M ใหญ่และ N ใหญ่)

Precompute Smallest Prime Factor (SPF) ด้วย Sieve จน √M หรือ M -> Factorize แต่ละตัวได้ O(log M) แทน O(√M) แต่สำหรับ Constraints ปกติ (M ≤ 10⁵) วิธี √M พอครับ