หาผลรวมสูงสุดของจำนวนที่ต่างกันซึ่ง LCM เป็น N ใน C++

โจทย์

กำหนดจำนวน N หาผลรวมสูงสุดของจำนวนที่ต่างกันซึ่ง LCM (Least Common Multiple) ของพวกมันเท่ากับ N

ตัวอย่าง: N = 10 → ตัวประกอบ: 1, 2, 5, 10 → Sum = 18

วิธีการแก้ปัญหา

สังเกต: เพื่อให้ LCM = N ต้องเลือกเฉพาะตัวหารของ N เท่านั้น และเพื่อให้ผลรวมสูงสุด → ต้องเลือกตัวหารทั้งหมดของ N

อัลกอริทึม: หาตัวหารทุกคู่ของ N (iterate จน sqrt(N)) รวมตัวหารทั้งหมด

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

#include <iostream>
using namespace std;

int calcFactorSum(int N){
    int maxSum = 0;
    for (int i = 1; i*i <= N; i++){
        if (N % i == 0) {
            if (i == (N/i))
                maxSum = maxSum + i;
            else
                maxSum = maxSum + i + (N/i);
        }
    }
    return maxSum;
}

int main(){
    int N = 42;
    cout << "The sum of distinct numbers with LCM as " << N << " is " << calcFactorSum(N);
    return 0;
}

ผลลัพธ์

The sum of distinct numbers with LCM as 42 is 96