C++로 숫자의 모든 약수 곱 구하기

약수의 곱이란?

숫자 n이 주어졌을 때, n의 모든 약수를 찾아 그 약수들을 모두 곱한 결과를 반환하는 것이 이 문제의 목표입니다. 즉, 어떤 수의 '약수들의 곱'을 구하는 것입니다. 여기서 약수란 1을 포함하여 해당 숫자를 나머지 없이 완전히 나눌 수 있는 수를 의미합니다. 예를 들어 6의 약수는 1, 2, 3, 6입니다.

주어진 과제에 따라 숫자의 모든 약수의 곱을 구해야 합니다.

입력 − n = 18

출력 − 5832

설명 − 1 × 2 × 3 × 6 × 9 × 18 = 5832

입력 − n = 9

출력 − 27

설명 − 1 × 3 × 9 = 27

문제 해결 접근 방식

모든 약수를 하나씩 확인하는 대신, √n까지만 반복하면서 약수 쌍을 동시에 처리하면 효율적으로 문제를 해결할 수 있습니다. 접근 방법은 다음과 같습니다.

숫자 num을 입력받습니다.
i = 1부터 i × i ≤ num이 될 때까지 반복합니다.
num % i == 0이라면(즉, i가 약수라면) 다음을 확인합니다.
- 만약 num / i == i라면(제곱근인 경우) 같은 약수가 중복되므로 product = (product × i) % MAX로 한 번만 곱합니다.
- 그렇지 않다면 product를 (product × i) % MAX로 설정하고, 이어서 product를 (product × num / i) % MAX로 설정하여 약수 쌍(i와 num/i)을 모두 곱합니다.
최종 product를 반환합니다.

이 방식은 반복 횟수가 O(√n)으로 줄어들어 큰 수에 대해서도 빠르게 동작합니다.

알고리즘

시작
함수 long long productfactor(int num)
    단계 1 → product를 선언하고 1로 초기화
    단계 2 → i = 1부터 i * i <= num일 때까지 i를 1씩 증가시키며 반복
        만약 num % i == 0이면,
            만약 num / i == i이면,
                product를 (product * i) % MAX로 설정
            아니면,
                product를 (product * i) % MAX로 설정
                product를 (product * num / i) % MAX로 설정
    단계 3 → product 반환
함수 int main()
    단계 1 → n을 9로 선언 및 초기화
    단계 2 → productfactor(n)의 결과 출력
종료

예제 코드

#include <stdio.h>
#define MAX 1000000000
// 약수들의 곱을 구하는 함수
long long productfactor(int num){
    long long product = 1;
    for (int i = 1; i * i <= num; i++){
        if (num % i == 0){
            // 같은 약수(제곱근)는 한 번만 곱한다
            if (num / i == i)
                product = (product * i) % MAX;
            // 그렇지 않으면 두 약수를 모두 곱한다
            else {
                product = (product * i) % MAX;
                product = (product * num / i) % MAX;
            }
        }
    }
    return product;
}
int main(){
    int n = 9;
    printf("%lld\n", productfactor(n));
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −