C++에서 숫자가 41로 나누어 떨어지는지 확인하는 방법

이번 글에서는 주어진 숫자가 41로 나누어 떨어지는지 확인하는 프로그램을 C++로 작성해 보겠습니다. 예를 들어 104413920565933이라는 숫자가 있다고 가정해 봅시다. 이 숫자는 41로 나누어 떨어집니다.

큰 숫자를 직접 나눗셈으로 검증하기보다는, 수학적으로 증명된 41의 배수 판별법을 활용하면 훨씬 간단하게 확인할 수 있습니다.

41의 배수 판별법

어떤 숫자가 41로 나누어 떨어지는지 확인하려면 다음 규칙을 반복적으로 적용합니다.

• 숫자(또는 자릿수가 잘린 숫자)의 마지막 자릿수를 추출합니다.
• 나머지 부분(마지막 자릿수를 제거한 숫자)에서 마지막 자릿수 × 4를 뺍니다.
• 숫자가 충분히 작아질 때까지 위 과정을 반복합니다.

예시: 30873 판별하기

30873 → 3087 - 4×3 = 3075
3075 → 307 - 4×5 = 287
287 → 28 - 4×7 = 0

결과가 0이므로, 30873은 41로 나누어 떨어집니다.

최종 결과가 0 또는 41의 배수라면 원래 숫자도 41의 배수입니다.

C++ 구현 코드

#include <iostream>
#include <algorithm>
using namespace std;

bool isDivisibleBy41(long long int n) {
    while (n / 100) {
        int last = n % 10;      // 마지막 자릿수 추출
        n /= 10;                // 숫자 잘라내기 (truncation)
        n -= last * 4;          // 마지막 자릿수 × 4를 빼기
    }
    return (n % 41 == 0);
}

int main() {
    long long number = 104413920565933;
    if (isDivisibleBy41(number))
        cout << "Divisible";       // 나누어 떨어짐
    else
        cout << "Not Divisible";   // 나누어 떨어지지 않음
}

실행 결과

Divisible

코드 동작 원리

위 코드의 핵심 로직은 다음과 같습니다.

• n % 10으로 현재 숫자의 일의 자릿수를 얻습니다.
• n /= 10으로 일의 자릿수를 제거한 나머지 숫자를 만듭니다.
• n -= last * 4를 통해 판별 규칙에 따라 값을 갱신합니다.

while (n / 100) 조건은 숫자가 두 자리 이상일 때만 반복하도록 하여, 두 자리 숫자가 되면 반복문을 종료하고 해당 값이 41의 배수인지 최종 검사합니다. 이 방법은 long long 범위의 매우 큰 숫자도 나눗셈 연산 없이 빠르게 판별할 수 있다는 장점이 있습니다.