C++で数値Nを割り切る桁の個数を数える方法

整数 N が与えられ、その数値を構成する各桁のうち、元の数値 N を割り切るものの個数を求めることを考えます。

注意すべきポイント

• 桁が「0」である場合は無視します。つまり、0 に対してはカウントを増やしません。

• 同じ数字が複数回現れ、かつそれが数値を割り切る場合には、出現した回数だけカウントします。たとえば 2240 という数値の場合、0 以外のすべての桁が 2240 を割り切ることができ、2 は2回出現しているので、2 に関するカウントは 2 になります。

入力 − number = 2240

出力 − カウントは 3

説明 − 数値を桁に分解すると 2、2、4、0 となります。まず 2 が 2240 を割り切るかどうかを確認し、割り切れるならカウントを1増やし、そうでなければ次の桁へ進みます。この数値では 2、2、4 が 2240 を割り切るため、カウントは 3 になります。なお、0 はどのような場合でも無視します。

入力 − number = 755

出力 − カウントは 2

説明 − 数値を桁に分解すると 7、5、5 となります。7 は 755 を割り切れないためカウントせずに次へ進み、5 と 5 はそれぞれ 755 を割り切るため、最終的なカウントは 2 になります。

プログラムで採用しているアプローチ

• 数値を整数型変数(ここでは num)に入力として受け取ります。

• num が 0 より大きい間、ループ処理を続けます。

• ループの中で数値を一桁ずつ取り出し、その値を変数 rem に格納します。

• rem が元の数値を割り切れるかどうかを判定し、割り切れる場合はカウント変数を 1 増やし、割り切れない場合はそのままにします。

• この判定は rem が 0 より大きいときにのみ行います。0 を無視するというルールに従うだけでなく、0 による除算(ゼロ除算)を避ける意味もあります。

コード例

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

int count(int num){
    int a = num;
    int count = 0, rem;
    while(a > 0){
        rem = a % 10;
        if(rem > 0){
            if(num % rem == 0){
                count++;
            }
        }
        a = a / 10;
    }
    return count;
}

int main(){
    int num = 2240;
    cout << "与えられた数値 " << num << " を割り切る桁の個数は: " << count(num);
    return 0;
}

実行結果

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

与えられた数値 2240 を割り切る桁の個数は: 3

計算量

このアルゴリズムは、数値の各桁を一度ずつ調べるだけでよいため、桁数を d とすると時間計算量は O(d) となり、追加のメモリも定数しか使わないため空間計算量は O(1) です。非常に効率的なアプローチと言えます。