C++에서 매우 큰 숫자가 5로 나누어 떨어지는지 확인하는 방법

이 글에서는 주어진 숫자가 5로 나누어 떨어지는지 확인하는 방법을 알아보겠습니다. 여기서 다루는 숫자는 일반적인 정수 자료형으로 표현할 수 없을 만큼 매우 큰 수이기 때문에, 숫자를 문자열(string) 형태로 저장하여 처리합니다.

5의 배수 판별 원리

5의 배수 판별은 의외로 간단합니다. 복잡한 나눗셈 연산을 할 필요 없이, 숫자의 마지막 자릿수가 0 또는 5인지만 확인하면 됩니다.

예를 들어 10, 15, 120, 345 같은 숫자는 모두 일의 자리가 0 또는 5이며, 실제로 5로 나누어 떨어집니다. 이 성질 덕분에 아무리 큰 숫자라도 마지막 한 글자만 검사하면 되므로, 문자열로 저장된 거대한 숫자도 손쉽게 판별할 수 있습니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

bool isDiv5(string num) {
    int n = num.length();
    // 마지막 자릿수가 '5' 또는 '0'이 아니라면 5의 배수가 아님
    if(num[n - 1] != '5' && num[n - 1] != '0')
        return false;
    return true;
}

int main() {
    string num = "154484585745184258458158245285265";
    if(isDiv5(num)) {
        cout << "Divisible";      // 나누어 떨어짐
    } else {
        cout << "Not Divisible";  // 나누어 떨어지지 않음
    }
}

코드 설명

• isDiv5() 함수는 문자열로 전달받은 숫자의 길이를 구한 뒤, 마지막 문자(num[n - 1])를 검사합니다.
• 마지막 문자가 '5'나 '0'이 아니면 false를 반환하여 5의 배수가 아님을 알립니다.
• 그 외의 경우에는 true를 반환하여 5로 나누어 떨어짐을 의미합니다.

실행 결과

Divisible

위 예제에서 사용된 33자리 숫자 154484585745184258458158245285265는 마지막 자릿수가 5이므로, 프로그램은 "Divisible"(나누어 떨어짐)을 출력합니다.

마무리

이처럼 큰 수의 배수 판별 문제는 숫자를 직접 나누지 않고 자릿수의 특성을 이용하면 간단하게 해결할 수 있습니다. 시간 복잡도는 문자열의 마지막 문자 하나만 확인하므로 O(1)로 매우 효율적입니다. 같은 원리를 응용하면 2, 10 등 다른 수의 배수 판별 문제도 쉽게 풀 수 있습니다.