C++で最小の約数がKとなる範囲内の数値を数える方法

本チュートリアルでは、指定された範囲内にある数値のうち、「最小の約数(最小の素因数)」が K と一致するものの個数を求めるC++プログラムについて解説します。

問題の概要

範囲 [a, b] と整数 K が与えられたとき、この範囲に含まれる数値の中で「最小の約数が K であるもの」を数えるのが目的です。

ある数 n の最小の約数が K になるためには、次の2つの条件を満たす必要があります。

• n が K で割り切れること
• 2 以上 K 未満のいずれの整数でも n が割り切れないこと

また重要な点として、K が素数でない場合、条件を満たす数は存在しません(合成数が「最小の約数」となることはないため)。したがって、まず K が素数かどうかを判定する処理が必要になります。

実装例(C++)

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

// Kが素数かどうかを判定する関数
bool if_prime(int k){
    if (k <= 1)
        return false;
    for (int i = 2; i < k; i++)
        if (k % i == 0)
            return false;
    return true;
}

// numが2〜K-1のいずれでも割り切れず、Kで割り切れるかを判定する関数
int check(int num, int k){
    int flag = 1;
    for (int i = 2; i < k; i++) {
        if (num % i == 0)
            flag = 0;
    }
    if (flag == 1) {
        if (num % k == 0)
            return 1;
        else
            return 0;
    }
    else
        return 0;
}

// 条件を満たす数の個数を数える関数
int findCount(int a, int b, int k){
    int count = 0;
    if (!if_prime(k))
        return 0;
    else {
        int ans;
        for (int i = a; i <= b; i++) {
            ans = check(i, k);
            if (ans == 1)
                count++;
            else
                continue;
        }
    }
    return count;
}

int main(){
    int a = 2020, b = 6300, k = 29;
    cout << findCount(a, b, k);
    return 0;
}

コードの解説

1. if_prime 関数

引数として受け取った K が素数かどうかを判定します。K が 1 以下の場合は素数ではないため false を返し、2 から K-1 までの整数で順番に割り切れるかどうかを調べます。1つでも割り切れる数があれば false を返します。

2. check 関数

個々の数値 num について、2 から K-1 までのどの整数でも割り切れず(flag が 1 のまま)、かつ K で割り切れる場合に 1 を返します。これにより「num の最小の約数が K であること」を確認できます。

3. findCount 関数

まず K が素数であるかを確認し、素数でなければ即座に 0 を返します。素数である場合は、範囲 [a, b] 内の全ての数値に対して check 関数を呼び出し、条件を満たす数をカウントしていきます。

実行結果

28

この例では、範囲は [2020, 6300]、K は 29 です。この範囲内で「最小の素因数が 29 となる数」は 28 個存在するため、出力は 28 となります。

計算量と改善のヒント

現在の実装では、範囲内の各数値に対して 2 から K-1 までの除算を行うため、計算量は O((b − a + 1) × K) となります。範囲が広い場合や K が大きい場合は、以下のような工夫で高速化できます。

• check 関数の判定範囲を 2 から √K までに絞る(K の約数は√K以下に必ず存在するため)
• エラトステネスの篩などを用いて、あらかじめ小さい素数のリストを作成しておき、それらでのみ割り切れるかを判定する
• K で割り切れる最小の数(= K そのもの、または K の倍数のうち最初のもの)から K ずつ飛ばしながら候補を絞り込む

これらの最適化により、大きな入力に対しても効率的に動作するプログラムを実装できます。