C++에서 매우 큰 숫자가 15의 배수인지 확인하는 방법

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

15의 배수 판별 원리

어떤 수가 15의 배수라면, 그 수는 반드시 5의 배수이면서 동시에 3의 배수여야 합니다. 이 두 조건은 각각 다음과 같이 쉽게 확인할 수 있습니다.

• 5의 배수 판별: 숫자의 마지막 자릿수가 '0' 또는 '5'인지 확인합니다.
• 3의 배수 판별: 모든 자릿수의 합이 3으로 나누어 떨어지는지 확인합니다.

두 조건을 모두 만족하면 해당 숫자는 15의 배수입니다. 이 방식은 숫자가 아무리 커도 문자열만 순회하면 되므로 O(n) 시간 복잡도로 빠르게 판별할 수 있다는 장점이 있습니다.

C++ 구현 예제

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

bool isDiv15(string num){
    int n = num.length();
    // 마지막 자릿수가 0 또는 5가 아니면 5의 배수가 아님
    if(num[n - 1] != '5' && num[n - 1] != '0')
        return false;
    // 각 자릿수의 합 계산
    long sum = accumulate(begin(num), end(num), 0) - '0' * n;
    // 자릿수의 합이 3으로 나누어 떨어지면 3의 배수임
    if(sum % 3 == 0)
        return true;
    return false;
}

int main() {
    string num = "154484585745184258458158245285260";
    if(isDiv15(num)){
        cout << "Divisible";
    } else {
        cout << "Not Divisible";
    }
}

실행 결과

Divisible

코드 설명

isDiv15 함수는 먼저 문자열의 마지막 문자를 검사하여 5의 배수 여부를 확인합니다. 마지막 자릿수가 '0'이나 '5'가 아니면 즉시 false를 반환합니다.

다음으로 accumulate 함수를 사용해 모든 자릿수의 ASCII 값 합계를 구한 뒤, 문자 '0'의 값에 자릿수 개수를 곱한 값을 빼서 실제 숫자의 합을 계산합니다. 이 합이 3으로 나누어 떨어지면 그 수는 3의 배수입니다.

예제에서 사용한 33자리 숫자는 마지막 자릿수가 '0'이고 자릿수의 합이 3의 배수이므로, 최종적으로 "Divisible(나누어 떨어짐)"이 출력됩니다.