【C++】巨大な数が8で割り切れるかどうかを判定する方法

本記事では、非常に大きな数が8で割り切れるかどうかを判定する方法を解説します。判定対象となる数は非常に大きいため、通常の整数型では扱えず、文字列として受け取って処理します。

ある数が8で割り切れるかどうかは、下3桁で作られる数が8で割り切れるかどうかだけで判断できます。これは、1000が8の倍数であることから導かれる性質です。1000より上の位の部分は必ず8の倍数になるため、下3桁だけを確認すれば十分です。

アルゴリズムの手順

判定は以下の手順で行います。

1. 数値を文字列として受け取る
2. 文字列の末尾3文字を取り出し、それぞれの文字を数値に変換して整数値を組み立てる
3. その値を8で割った余りが0かどうかを確認する

C++による実装例

#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」の下3桁は「360」です。360 ÷ 8 = 45 となり余りが0なので、この数は8で割り切れると判定されます。

計算量について

この方法の利点は、文字列全体を走査する必要がない点です。末尾3桁のみを確認するため、計算量はO(1)の定数時間で済みます。数百桁・数千桁といった巨大な数でも、効率的に割り切り判定が可能です。