【C++入門】大きな数値が37で割り切れるかどうかを判定するプログラムの作り方

はじめに

このチュートリアルでは、与えられた大きな数値が37で割り切れるかどうかを判定するC++プログラムを作成します。

判定には、少し数学的な性質を利用します。それでは、問題を解くための手順を順番に見ていきましょう。

• 判定対象となる数値を用意します。
• 桁数が3で割り切れない場合は、先頭に「0」を追加して桁数を3の倍数にします。
• 数値を3桁ずつのグループに分割し、各グループの値をすべて合計します。
• その合計が37で割り切れるならば、元の数値も37で割り切れます。
• 合計が4桁以上になった場合は、手順2以降を繰り返します。
• 最後に、元の数値が37で割り切れるかどうかを出力します。

サンプルコード

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
bool isNumberDivisibleBy37(string number, int n) {
    if (number == "0") {
        return 0;
    }
    if (n % 3 == 1){
        number = "00"+ number;
        n += 2;
    }
    else if (n % 3 == 2){
        number = "0"+ number;
        n += 1;
    }
    int groups_sum = 0;
    while (n != 0){
        string group = number.substr(n - 3, n);
        int group_value = (group[0] - '0') * 100 + (group[1] - '0') * 10 + (group[2] - '0') * 1;
        groups_sum += group_value;
        n = n - 3;
    }
    if (groups_sum >= 1000) {
        string new_number = to_string(groups_sum);
        return isNumberDivisibleBy37(new_number, new_number.length());
    }
    else {
        return groups_sum % 37 == 0;
    }
}
int main() {
    string number = "4048675309";
    if (isNumberDivisibleBy37(number, 10)) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}

実行結果

上記のコードを実行すると、次のような出力が得られます。

Yes

まとめ

このように、3桁ごとのグループ合計を繰り返し計算することで、非常に大きな数値でも効率的に37の倍数かどうかを判定できます。本チュートリアルについて質問がある場合は、コメント欄でお気軽にお知らせください。