C++로 큰 수가 37로 나누어 떨어지는지 확인하는 방법

이 튜토리얼에서는 주어진 매우 큰 숫자가 37로 나누어 떨어지는지 확인하는 C++ 프로그램을 작성해 보겠습니다.

이 문제는 약간의 수학적 지식을 활용합니다. 핵심은 1000을 37로 나눈 나머지가 1이라는 성질입니다(999 = 27 × 37). 이 성질 덕분에 숫자를 오른쪽부터 세 자리씩 끊어 각 그룹의 값을 모두 더하더라도 원래 수의 37 배수 여부는 그대로 유지됩니다. 3의 배수 판별법에서 각 자릿수의 합을 구하는 것과 비슷한 원리라고 생각하면 이해하기 쉽습니다.

문제 해결 단계

숫자를 문자열 형태로 초기화합니다.
숫자의 길이가 3으로 나누어 떨어지지 않으면, 맨 앞에 0을 추가해 길이를 3의 배수로 맞춥니다.
숫자를 세 자리씩 그룹으로 나눈 뒤, 각 그룹의 값을 모두 더합니다.
구한 합이 37로 나누어 떨어지면 주어진 수도 37로 나누어 떨어집니다.
구한 합이 네 자리 이상이라면 2번 단계부터 다시 반복합니다.
최종 판정 결과를 출력합니다.

구현 예시

전체 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;
bool isNumberDivisibleBy37(string number, int n) {
    if (number == "0") {
        return 0;
    }
    if (n % 3 == 1){
        number = "00"+ number;
        n += 2;
    }
    else if (n % 3 == 2){
        number = "0"+ number;
        n += 1;
    }
    int groups_sum = 0;
    while (n != 0){
        string group = number.substr(n - 3, n);
        int group_value = (group[0] - '0') * 100 + (group[1] - '0') * 10 + (group[2] - '0') * 1;
        groups_sum += group_value;
        n = n - 3;
    }
    if (groups_sum >= 1000) {
        string new_number = to_string(groups_sum);
        return isNumberDivisibleBy37(new_number, new_number.length());
    }
    else {
        return groups_sum % 37 == 0;
    }
}
int main() {
    string number = "4048675309";
    if (isNumberDivisibleBy37(number, 10)) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}

실행 결과

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

Yes

동작 과정 살펴보기

예제로 사용한 4048675309가 실제로 어떻게 처리되는지 단계별로 확인해 보겠습니다.

숫자의 길이가 10이므로 앞에 0 두 개를 붙여 004048675309로 만듭니다.
세 자리씩 나누면 004 | 048 | 675 | 309가 되고, 이들의 합은 4 + 48 + 675 + 309 = 1036입니다.
합이 네 자리이므로 1036에 대해 같은 과정을 다시 적용합니다. 001 | 036 → 1 + 36 = 37
37은 37로 나누어 떨어지므로, 원래 수인 4048675309 역시 37로 나누어 떨어집니다.

마무리

이처럼 아주 큰 수를 직접 나눗셈하지 않아도 자릿수 그룹화 기법을 활용하면 37의 배수 여부를 빠르고 간단하게 판별할 수 있습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.