หาผลรวมของจำนวนและเฉพาะตัวประกอบมากที่สุดใน C++

โจทย์

ให้จำนวนเต็มบวก N ต้องการหาผลรวมของ N และเฉพาะตัวประกอบมากที่สุดของ N

ตัวอย่าง: N=26, เฉพาะตัวประกอบมากที่สุดคือ 13 → ผลรวม = 26+13 = 39

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

1. หาร 2 จนหมด เก็บ 2 เป็น maxPrime
2. ลูป i=3 ถึง sqrt(n) ก้าว 2 หารจนหมด อัปเดต maxPrime
3. ถ้า n ที่เหลือ > 2 → มันคือเฉพาะตัวประกอบมากที่สุด
4. คืนค่า N + maxPrime

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

#include <iostream>
#include <cmath>
using namespace std;

int maxPrimeFact(int n) {
    int num = n;
    int maxPrime = -1;
    while (n % 2 == 0) { maxPrime = 2; n /= 2; }
    for (int i = 3; i <= sqrt(n); i += 2) {
        while (n % i == 0) { maxPrime = i; n = n / i; }
    }
    if (n > 2) maxPrime = n;
    return maxPrime;
}

int getRes(int n) {
    int sum = maxPrimeFact(n) + n;
    return sum;
}

int main() {
    int n = 26;
    cout << "Sum of " << n << " and its max prime factor is: " << getRes(n);
}

ผลลัพธ์

Sum of 26 and its max prime factor is: 39