C++で巨大な数値が2・3・5で割り切れるかを判定する方法

本記事では、非常に大きな数値が2・3・5のすべてで割り切れるかどうかを判定する方法を解説します。対象となる数は桁数が非常に大きいため、通常の整数型では扱えません。そこで、数値を文字列（string）として受け取り、各桁を調べることで判定を行います。

判定の考え方：最小公倍数を使う

ある数が2・3・5のすべてで割り切れるということは、その数がこれらの最小公倍数（LCM）で割り切れることと同じです。

• 2、3、5の最小公倍数は 30
• つまり「30で割り切れるか」を判定すればよい

さらに、30で割り切れる条件は次のように分解できます。

1. 10で割り切れる → 最後の桁（1の位）が「0」である
2. 3で割り切れる → 全桁の数字の合計が3の倍数である

この2つの条件を満たせば、その数は30（＝2×3×5）で割り切れると判断できます。

C++での実装例

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

bool isDiv30(string num){
    int n = num.length();
    // 条件1: 最後の桁が '0' かどうか（10で割り切れるか）
    if(num[n - 1] != '0')
        return false;
    // 条件2: 各桁の合計が3の倍数かどうか
    long sum = accumulate(begin(num), end(num), 0) - '0' * n;
    if(sum % 3 == 0)
        return true;
    return false;
}

int main() {
    string num = "353730746028908374890";
    if(isDiv30(num)){
        cout << "Divisible";      // 割り切れる
    } else {
        cout << "Not Divisible";  // 割り切れない
    }
}

実行結果

Divisible

コードのポイント

• num[n - 1] != '0' で文字列の末尾の文字を確認し、10の倍数かどうかを判定しています。
• accumulate を使って全桁のASCIIコード値を合計し、'0' * n を引くことで実際の数字の合計を求めています。
• この手法なら、どれほど桁数が大きい数でも文字列として処理できるため、オーバーフローの心配がありません。

計算量は文字列の長さに比例する O(n) であり、巨大な数値でも高速に判定できます。