【C++】k-ラフ数（k-ジャグ数）の判定方法をわかりやすく解説

k-ラフ数（k-ジャグ数）とは？

ある整数の最小の素因数が、指定された値 k 以上であるとき、その数は k-ラフ数（k-rough number） または k-ジャグ数（k-jagged number） と呼ばれます。

例えば、75 の素因数は 3、5、5 なので、最小の素因数は 3 です。したがって、75 は「3-ラフ数」ですが、「5-ラフ数」ではありません。

このチュートリアルでは、与えられた数 n が k-ラフ数であるかどうかを判定する C++ プログラムを作成します。

解決の手順

• 数値 n と k を初期化します。
• n の約数となるすべての素数を見つけ、ベクターに格納します。
• ベクターの先頭要素（＝最小の素因数）を取得し、k と比較することで、n が k-ラフ数かどうかを判定します。

C++での実装例

それでは、実際のコードを見てみましょう。

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

// 素数判定関数
bool isPrime(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

// n の約数の中から素数をすべて取得する関数
vector<int> getPrimes(int n) {
    vector<int> primes;
    for (int i = 2; i < n; i++) {
        if (n % i == 0 && isPrime(i)) {
            primes.push_back(i);
        }
    }
    return primes;
}

// n が k-ラフ数かどうかを判定する関数
bool isRoughNumber(int n, int k) {
    vector<int> primes = getPrimes(n);
    return primes[0] >= k;
}

int main() {
    int n = 75, k = 3;
    if (isRoughNumber(n, k)) {
        cout << n << " is a " << k << " rough number" << endl;
    } else {
        cout << n << " is not a " << k << " rough number" << endl;
    }
    return 0;
}

実行結果

上記のプログラムを実行すると、次のような出力が得られます。

75 is a 3 rough number

75 の最小の素因数は 3 であり、これは k = 3 以上であるため、「3-ラフ数」と正しく判定されています。

まとめ：さらに効率よくするには

実は、すべての素因数をベクターに格納する必要はありません。n の最小の素因数だけを見つけ、それを k と比較すれば十分です。2 から順に n を割り切れる数を探し、最初に見つかった時点で判定を返せばよいため、メモリ使用量と計算時間の両方を大幅に削減できます。

ぜひ、この最適化されたアプローチで自分でも実装してみてください。

本チュートリアルについてご不明な点やご質問がある場合は、コメント欄でお気軽にお知らせください。