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

本記事では、与えられた数値が23で割り切れるかどうかを判定するC++プログラムを紹介します。例えば、1191216という数値は23で割り切れることが知られています。

この割り切り判定を行うには、以下のルールに従います。

• 毎回、数値（桁を削った数）から末尾の一桁を取り出します。
• 取り出した末尾の一桁に7を掛けた値を、桁を削った残りの数に加算します。
• 必要な範囲でこれらの手順を繰り返します。

実際に17043という数値で確認してみましょう。

17043 の場合 → 1704 + 7 × 3 = 1725
1725 の場合 → 172 + 7 × 5 = 207
207 は 9 × 23 なので、17043 は23で割り切れる

最終的に得られた数値が23の倍数であれば、元の数値も23で割り切れることになります。これは、10 ≡ 10 (mod 23) であることと、10 × 7 = 70 ≡ 1 (mod 23) という性質を利用した判定法です。

C++による実装例

#include <iostream>
#include <algorithm>
using namespace std;
bool isDivisibleBy23(long long int n) {
    while (n / 100) {
        int last = n % 10; // 末尾の一桁を取得
        n /= 10; // 数値の桁を削る
        n += last * 7; // 末尾の桁 × 7 を加算
    }
    return (n % 23 == 0);
}
int main() {
    long long number = 1191216;
    if(isDivisibleBy23(number))
        cout << "Divisible";
    else
        cout << "Not Divisible";
}

実行結果

Divisible

このアルゴリズムでは、数値が2桁以下になるまで処理を繰り返し、最終的な数値に対して23での剰余を計算することで割り切れるかどうかを判定しています。大きな数値でも毎回一桁ずつ減らしていくため、効率的に判定できるのが特徴です。