C++에서 아주 큰 숫자가 2, 3, 5로 나누어 떨어지는지 확인하는 방법

이 글에서는 어떤 숫자가 2, 3, 5로 모두 나누어 떨어지는지 확인하는 방법을 알아봅니다. 여기서 다루는 숫자는 일반적인 정수 자료형으로 담을 수 없을 만큼 매우 큰 수이기 때문에, 문자열(string) 형태로 입력받아 처리합니다.

핵심 아이디어: 최소공배수 30 활용하기

어떤 수가 2, 3, 5로 모두 나누어 떨어지려면, 그 수가 반드시 2, 3, 5의 최소공배수(LCM)로도 나누어 떨어져야 합니다. 2, 3, 5의 최소공배수는 30이므로, 결국 해당 숫자가 30으로 나누어 떨어지는지만 확인하면 됩니다.

30으로 나누어 떨어지는 두 가지 조건

숫자가 30으로 나누어 떨어지려면 다음 조건을 동시에 만족해야 합니다.

• 10으로 나누어 떨어질 것 — 마지막 자릿수가 0이어야 합니다.
• 3으로 나누어 떨어질 것 — 모든 자릿수의 합이 3으로 나누어 떨어져야 합니다.

두 조건은 각각 마지막 한 자리와 전체 자릿수의 합만 보면 되므로, 숫자가 아무리 커도 문자열 기반으로 빠르게 판별할 수 있습니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
bool isDiv30(string num){
    int n = num.length();
    // 조건 1: 마지막 자릿수가 0인지 확인 (10의 배수)
    if(num[n - 1] != '0')
        return false;
    // 조건 2: 모든 자릿수의 합이 3의 배수인지 확인
    long sum = accumulate(begin(num), end(num), 0) - '0' * n;
    if(sum % 3 == 0)
        return true;
    return false;
}
int main() {
    string num = "353730746028908374890";
    if(isDiv30(num)){
        cout << "Divisible";   // 나누어 떨어짐
    } else {
        cout << "Not Divisible";  // 나누어 떨어지지 않음
    }
}

실행 결과

Divisible

예제에 사용된 숫자 353730746028908374890는 마지막 자릿수가 0이고, 각 자릿수의 합이 3의 배수이므로 30으로 나누어 떨어집니다. 따라서 프로그램은 Divisible(나누어 떨어짐)을 출력합니다.

정리

매우 큰 숫자의 배수 여부를 판별할 때는 숫자를 직접 정수로 변환하지 말고, 문자열 상태에서 자릿수 규칙(마지막 자릿수 확인 + 자릿수 합 계산)을 활용하면 효율적으로 해결할 수 있습니다. 이 방법은 자릿수가 수백 자리를 넘어가는 초대형 숫자에도 동일하게 적용됩니다.