Maximum Sum After Repeatedly Dividing N by a Divisor ใน C++

ปัญหา

มีจำนวนเต็ม N หารซ้ำๆ ด้วยตัวหารจนได้ 1 หาผลรวมของค่าทุกขั้นตอน (รวม N เริ่มต้น) ให้สูงสุด

ตัวอย่าง

N = 12
12/2=6, 6/2=3, 3/3=1
Sum = 12+6+3+1 = 22

ข้อสังเกต

เพื่อให้ผลรวมสูงสุด ควรหารด้วย ตัวหารที่น้อยที่สุด (smallest divisor) ทุกครั้ง

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

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

int smallestDivisor(int n){
    int mx = sqrt(n);
    for (int i = 2; i <= mx; i++)
        if (n % i == 0) return i;
    return n;
}

int calculateMaxSum(int n) {
    long long maxSum = n;
    while (n > 1) {
        int divisor = smallestDivisor(n);
        n /= divisor;
        maxSum += n;
    }
    return maxSum;
}

int main(){
    int N = 12;
    cout << "The maximum sum after repeatedly dividing " << N << " by divisor is " << calculateMaxSum(N);
    return 0;
}

ผลลัพธ์

The maximum sum after repeatedly dividing 12 by divisor is 22