Javaで、元の数と共通する桁を1つ以上持つ約数の個数を数える方法

整数 num が与えられたとき、その約数をすべて求め、さらに「num の各桁に現れる数字を少なくとも1つ含む約数」がいくつあるかを数えるのがこの課題です。

入力例と出力例

例1

入力: num = 24
出力: カウントは 4

解説: 以下の手順で求めます。

• まず、与えられた数の約数をすべて求めます。

  • 24 の約数は 1, 2, 3, 4, 6, 8, 12, 24 です。

• 次に、どの約数が num の桁に含まれる数字と一致しているかを確認します。

  • 24 の桁は「2」と「4」なので、これらの数字を含む約数は 2, 4, 12, 24 の4つです。

例2

入力: num = 10
出力: カウントは 2

解説: 以下の手順で求めます。

• まず、与えられた数の約数をすべて求めます。

  • 10 の約数は 1, 2, 5, 10 です。

• 次に、どの約数が num の桁に含まれる数字と一致しているかを確認します。

  • 10 の桁は「1」と「0」なので、該当する約数は 1 と 10 の2つです。

アルゴリズムの考え方

1. num を読み込み、各桁の出現状況を記録するためのサイズ10の配列 arr を用意します。arr[d] = 1 は「数字 d が num に含まれている」ことを意味します。
2. 1 から √num までループし、i が num の約数かどうかを判定します。
3. i が約数であれば digitCheck(i) を呼び出し、i の各桁に num と共通の数字があるかを調べ、あればカウントを1増やします。
4. n / i != i の場合（平方根の重複を除くため）、ペアとなる約数 n/i も同様にチェックします。
5. 最終的なカウントを出力します。

Javaでの実装例

package test;
import java.util.*;
import java.util.Scanner;

public class Testdigit {
    // m の各桁に、num に含まれる数字と同じものがあるかをチェックする
    static int digitCheck(int m, int arr[]) {
        while (m > 0) {
            if (arr[m % 10] == 1) {
                return 1;
            }
            m = m / 10;
        }
        return 0;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.print("Enter any number: ");
        int n = scan.nextInt();

        // n に含まれる各桁の数字を配列に記録
        int arr[] = new int[10];
        int m = n;
        while (m > 0) {
            arr[m % 10] = 1;
            m = m / 10;
        }

        int count = 0;
        // 1 から √n まで調べて約数を効率よく列挙
        for (int i = 1; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                if (digitCheck(i, arr) == 1) {
                    count++;
                }
                if (n / i != i) {
                    if (digitCheck(n / i, arr) == 1) {
                        count++;
                    }
                }
            }
        }
        System.out.println("Count " + count);
    }
}

実行結果

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

Enter any number: 24
Count 4

計算量について

約数の列挙を √n までのループで行っているため、時間計算量は O(√n × d) となります（d は各数値の桁数）。使用するのはサイズ10の固定長配列だけなので、空間計算量は O(1) です。全約数を1つずつ試す O(n) の素朴な方法に比べ、大きな数でも高速に動作する点がポイントです。

まとめ

この問題は「約数の高速な列挙」と「桁ごとの数字の照合」という2つの基本的なテクニックを組み合わせることで解けます。配列による桁の管理と √n までの探索を覚えておくと、似たような数値処理の問題にも応用できます。