C++로 숫자와 그 최대 소인수의 합 구하기

문제 개요

양수 n이 주어졌을 때, n 자신과 n의 최대 소인수(最大 素因數)를 더한 값을 구하는 문제입니다. 예를 들어 숫자가 26이라면, 26의 소인수는 2와 13이므로 최대 소인수는 13입니다. 따라서 답은 26 + 13 = 39가 됩니다.

접근 방법

풀이 방법은 매우 직관적입니다.

1. 주어진 수를 소인수분해하여 가장 큰 소인수를 찾습니다.
2. 찾은 최대 소인수에 원래 수 n을 더한 값을 반환합니다.

소인수분해는 다음 단계로 진행됩니다.

- 먼저 2로 나누어 떨어지는 동안 계속 2로 나누며 최대 소인수를 2로 갱신합니다.
- 이후 3부터 √n까지 홀수만 검사하면서 나누어 떨어지는 인수로 나누고, 해당 값을 최대 소인수로 갱신합니다.
- 마지막으로 남은 n이 2보다 크다면 그 값 자체가 소수이므로 최대 소인수가 됩니다.

이 알고리즘의 시간 복잡도는 O(√n)으로 효율적입니다.

예제 코드

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

int maxPrimeFact(int n){
    int maxPrime = -1;
    // 2로 나누어 떨어지는 동안 반복
    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;
        }
    }
    // 남은 수가 2보다 크면 그 자체가 소수
    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

코드 설명

maxPrimeFact() 함수는 입력받은 수를 소인수분해하면서 지금까지 발견한 가장 큰 소인수를 추적합니다. 2를 제외한 모든 소수는 홀수이므로, 반복문을 3부터 시작해 2씩 증가시키면 불필요한 짝수 검사를 생략할 수 있어 성능이 향상됩니다. 마지막 조건문에서 남은 값이 2보다 클 경우, 이는 분해되지 않은 소수이므로 곧바로 최대 소인수로 처리합니다.

getRes() 함수는 이렇게 구한 최대 소인수에 원래 수를 더해 최종 결과를 반환하며, main() 함수에서 n = 26에 대한 결과를 출력합니다.