C++로 판별하는 산술수(Arithmetic Number): 개념과 구현 방법

산술수(Arithmetic Number)란?

산술수(Arithmetic Number)는 모든 양의 약수의 평균이 정수가 되는 수를 의미합니다. 즉, 어떤 수 n에 대해 약수의 합을 약수의 개수로 나누었을 때 나누어떨어지면, 그 수 n은 산술수입니다.

예시를 통해 개념을 더 자세히 이해해 보겠습니다.

입력 : n = 6
출력 : YES
설명 :
약수는 1, 2, 3, 6
약수의 합 = 1+2+3+6 = 12
약수의 개수 = 4
약수의 합 ÷ 약수의 개수 = 12 / 4 = 3

위 예제에서 6의 약수 평균은 3으로 정수이므로, 6은 산술수입니다. 참고로 1, 3, 5, 7, 14, 15처럼 서로 다른 소인수를 최대 두 개까지만 가지는 수는 항상 산술수가 됩니다.

알고리즘

산술수 여부를 판별하는 절차는 다음과 같습니다.

1단계 : 약수의 합을 계산하여 sum 변수에 저장합니다.
2단계 : 약수의 총 개수를 구합니다.
3단계 : 약수의 합을 약수의 개수로 나눈 나머지가 0인지 확인합니다.
4단계 : 나머지가 0이면 YES를 출력하고, 그렇지 않으면 NO를 출력합니다.

C++ 구현 예제

아래 코드는 에라토스테네스의 체(Sieve of Eratosthenes)를 활용해 약수의 개수를 효율적으로 구하고, 소인수분해 기반 공식으로 약수의 합을 계산한 뒤 산술수 여부를 판별합니다.

#include <bits/stdc++.h>
using namespace std;
void SieveOfEratosthenes(int n, bool prime[], bool primesquare[], int a[]);
int countDivisors(int n);
int sumofFactors(int n);

int main(){
    int n = 46;
    int divcount = countDivisors(n);
    int divsum = sumofFactors(n);
    if(divsum % divcount == 0){
        cout<<"YES";
    }
    else
        cout<<"NO";
    return 0;
}

// 에라토스테네스의 체로 소수 배열과 소수 제곱 배열 생성
void SieveOfEratosthenes(int n, bool prime[], bool primesquare[], int a[]){
    for (int i = 2; i <= n; i++)
        prime[i] = true;
    for (int i = 0; i <= (n * n + 1); i++)
        primesquare[i] = false;
    prime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (prime[p] == true) {
            for (int i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }
    int j = 0;
    for (int p = 2; p <= n; p++) {
        if (prime[p]) {
            a[j] = p;
            primesquare[p * p] = true;
            j++;
        }
    }
}

// 약수의 개수를 계산하는 함수
int countDivisors(int n){
    if (n == 1)
        return 1;
    bool prime[n + 1], primesquare[n * n + 1];
    int a[n];
    SieveOfEratosthenes(n, prime, primesquare, a);
    int ans = 1;
    for (int i = 0;; i++) {
        if (a[i] * a[i] * a[i] > n)
            break;
        int cnt = 1;
        while (n % a[i] == 0){
            n = n / a[i];
            cnt = cnt + 1;
        }
        ans = ans * cnt;
    }
    if (prime[n])
        ans = ans * 2;
    else if (primesquare[n])
        ans = ans * 3;
    else if (n != 1)
        ans = ans * 4;
    return ans;
}

// 약수의 합을 계산하는 함수
int sumofFactors(int n){
    int res = 1;
    for (int i = 2; i <= sqrt(n); i++) {
        int count = 0, curr_sum = 1;
        int curr_term = 1;
        while (n % i == 0) {
            count++;
            n = n / i;
            curr_term *= i;
            curr_sum += curr_term;
        }
        res *= curr_sum;
    }
    if (n >= 2)
        res *= (1 + n);
    return res;
}

실행 결과

YES

n = 46일 때 약수는 1, 2, 23, 46이며, 약수의 합은 72, 약수의 개수는 4입니다. 72 ÷ 4 = 18로 나누어떨어지므로 46은 산술수이며, 프로그램은 YES를 출력합니다.