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

개요

이 글에서는 주어진 수가 8로 나누어 떨어지는지 판별하는 방법을 알아봅니다. 여기서 다루는 수는 int나 long long 같은 기본 정수 자료형으로 담기 어려울 정도로 크기 때문에, 문자열(string) 형태로 입력받아 처리합니다.

핵심 아이디어

어떤 수가 8로 나누어 떨어지는지 확인하는 규칙은 매우 간단합니다.

수의 마지막 세 자리로 만들어진 값이 8로 나누어 떨어지면, 해당 수 전체도 8로 나누어 떨어집니다.

그 이유는 다음과 같습니다. 임의의 수 N을 마지막 세 자리를 제외한 앞부분 A와 마지막 세 자리 B로 나누면 N = 1000 × A + B로 표현할 수 있습니다. 이때 1000은 8의 배수(1000 ÷ 8 = 125)이므로, N이 8로 나누어 떨어지는지 여부는 오직 B에 의해서만 결정됩니다.

구현 예제

아래 코드는 문자열로 표현된 큰 수의 마지막 세 자리를 추출해 정수 값으로 변환한 뒤, 그 값이 8로 나누어 떨어지는지 검사합니다.

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

bool isDiv8(string num){
    int n = num.length();
    // 마지막 세 자리를 정수로 변환
    int last_three_digit_val = (num[n-3] - '0') * 100 
                             + (num[n-2] - '0') * 10 
                             + (num[n-1] - '0');
    if(last_three_digit_val % 8 == 0)
        return true;
    return false;
}

int main() {
    string num = "1754586672360";   // 매우 큰 수를 문자열로 저장
    if(isDiv8(num)){
        cout << "Divisible";        // 나누어 떨어짐
    }else{
        cout << "Not Divisible";    // 나누어 떨어지지 않음
    }
}

출력 결과

Divisible

예제의 수 1754586672360은 마지막 세 자리가 360이고, 360 ÷ 8 = 45이므로 8로 나누어 떨어짐을 확인할 수 있습니다.

시간 복잡도

문자열의 길이에 관계없이 항상 마지막 세 자리만 확인하면 되므로, 시간 복잡도는 O(1)입니다. 따라서 수가 아무리 커도 상수 시간 안에 판별할 수 있다는 장점이 있습니다.