C++で数値が41で割り切れるかどうかを判定する方法

本記事では、与えられた数値が41で割り切れるかどうかを判定するC++プログラムを紹介します。例として、104413920565933という大きな数値を取り上げます。この数値は実は41で割り切れます。

巨大な数値を実際に割り算せずに判定するには、次の「41の倍数判定法」を利用します。

41で割り切れるかの判定ルール

• 元の数（または切り捨て後の数）から、末尾の一桁を取り出す。
• 残りの数（末尾を切り捨てた数）から、「4 × 取り出した一桁」を引く。
• 必要な限り、この手順を繰り返す。

最終的に得られた小さな数が41の倍数であれば、元の数も41で割り切れることになります。これは「10a + b が41の倍数 ⟺ a − 4b が41の倍数」という性質に基づいています（10 × (a − 4b) = 10a − 40b ≡ 10a + b (mod 41) となるためです）。

計算例：30873の場合

30873 → 3087 − 4×3 = 3075
3075 → 307 − 4×5 = 287
287 → 28 − 4×7 = 0
0は41の倍数なので、30873は41で割り切れる

このように、数値をどんどん小さくしながら判定できるのがこの方法の利点です。

C++プログラム例

#include <iostream>
#include <algorithm>
using namespace std;
bool isDivisibleBy41(long long int n) {
    while (n / 100) {
        int last = n % 10;
        n /= 10; // 末尾の一桁を切り捨てる
        n -= last * 4;
    }
    return (n % 41 == 0);
}
int main() {
    long long number = 104413920565933;
    if(isDivisibleBy41(number))
        cout << "Divisible";
    else
        cout << "Not Divisible";
}

実行結果

Divisible

このプログラムでは、whileループ内で毎回末尾の一桁を取り出し、残りの数から「4 × その一桁」を引いていくことで、数値を効率的に縮小しています。数値が十分に小さくなった時点で41による剰余を計算し、割り切れるかどうかを返します。long long型を使用することで、104413920565933のような15桁の大きな整数にも対応できます。