C++で[1, N]の範囲に含まれる一意な素因数の最大個数を求める方法

この記事では、与えられた範囲 [1, N] 内の数が持ちうる「一意な素因数（重複しない素因数）」の最大個数を求める問題を扱います。

まず、例を使って問題を具体的に理解しましょう。

入力例と出力例

• 入力 − N = 100
• 出力 − 3

説明 − 範囲 [1, 100] の中から 30 を考えてみます。

30 = 2 × 3 × 5 となり、素因数はすべて異なる3つです。したがって、範囲 [1, 100] において一意な素因数は最大で3個存在します。

• 入力 − N = 300
• 出力 − 4

N = 300 の場合は、2 × 3 × 5 × 7 = 210 ≤ 300 となるため、4つの異なる素因数を持つ数（210など）が範囲内に存在し、答えは4になります。

アルゴリズムの考え方

このプログラムでは以下の手順で問題を解きます。

1. 関数 MaxPrime() の冒頭で、N < 2 であるかどうかを判定します。該当する場合は 0 を返して終了します。
2. 次に、エラトステネスの篩（ふるい）を用いて、N までのすべての素数を求めます。
3. 積を格納する変数 pro = 1 と、最終的な答えを格納する変数 max = 0 を int 型で初期化します。
4. エラトステネスの篩の処理の中で、pro *= p; と書くことで、積が N より小さくなっている間、先頭から順に素数を掛け合わせていきます。
5. pro > N となった時点で max を返します。それ以外の場合は max に 1 を加算します。
6. 篩の処理が完了した後も、最後に max を返します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
int MaxPrime(int N){
    if (N < 2)
        return 0;
    // エラトステネスの篩を使用
    bool Arr[N+1];
    memset(Arr, true, sizeof(Arr));
    int pro = 1, max = 0;
    for (int p=2; p*p<=N; p++){
        if (Arr[p] == true){
            for (int i=p*2; i<=N; i += p)
                Arr[i] = false;
            /* 積がNより小さい間、先頭の素数を掛け合わせる */
            pro *= p;
            if (pro > N)
                return max;
            max++;
        }
    }
    return max;
}
// メイン関数
int main(){
    int N = 300;
    cout << MaxPrime(N);
    return 0;
}

実行結果

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

4

補足：なぜこの方法が正しいのか

異なる素因数をできるだけ多く持つには、できるだけ小さな素数から順に掛け合わせた数（最小の数）が範囲内に収まるかを確認すればよいことになります。つまり、2 × 3 × 5 × 7 × … というように小さい素数から順番に掛けていき、その積が初めて N を超えた直前の素因数の個数が答えとなります。計算量はエラトステネスの篩により O(N log log N) 程度に抑えられ、効率的に求められます。