C++で数を割り切る桁の個数を求める方法

問題の概要

ある整数が与えられたとき、その数を割り切る桁（各桁の数字）の個数を数える問題です。例として、数が 1012 の場合を考えてみましょう。この場合、答えは 3 となります。1、1、2 の3つの桁がそれぞれ 1012 を割り切れるためです。

解法のアプローチ

この問題を解くには、剰余演算（% 演算子）を使って数の各桁を1つずつ取り出し、元の数がその桁の値で割り切れるかどうかを判定します。割り切れる場合はカウンターを1つ増やします。なお、桁が 0 の場合は 0 で割ることができないため、その桁はスキップ（無視）します。

アルゴリズムの流れ

1. 元の数のコピーを作成し、0 になるまでループを繰り返します。
2. 各ループで 10 で割った余りを求め、その桁の数字を取得します。
3. 桁が 0 でない場合、元の数をその桁で割った余りが 0 であればカウンターを増やします。
4. 数を 10 で割って、次の桁へ処理を進めます。

コード例

#include<iostream>
using namespace std;

int countDivDigit(int num) {
    int count = 0;
    int temp = num;
    while (temp) {
        int div = temp % 10;      // 現在の桁の数字を取得
        if (div != 0) {           // 0 の桁は除外
            if (num % div == 0)   // その桁で割り切れるか判定
                count++;
        }
        temp /= 10;               // 次の桁へ進む
    }
    return count;
}

int main() {
    int num = 1012;
    cout << "Number of digits that divides " << num << " evenly, is: " << countDivDigit(num);
}

出力

Number of digits that divides 1012 evenly, is: 3

計算量について

このアルゴリズムは数の桁数だけループを回すため、時間計算量は O(log₁₀ n) となり、非常に効率的です。また、補助的な変数は定数個しか使用しないため、空間計算量は O(1) です。

まとめ

剰余演算と除算を組み合わせることで、各桁の数字を簡単に取り出すことができます。0 による除算エラーを避けるために 0 の桁を必ず除外する点が、この種の問題における重要なポイントです。