【C++】1からNまでの対数計算に必要なログ値の最小数を求めるアルゴリズム

対数には log(x*y) = log(x) + log(y) という重要な性質があります。この性質を利用すると、「1からNまでのすべての対数値を計算するために、最低いくつの対数値を直接求めればよいか」という興味深い問題を考えることができます。

例として、Nが6の場合を考えてみましょう。このとき答えは 3 になります。

• まず log(1) は常に0であるため、計算対象から除外します。
• log(2) と log(3) は素数なので、独立に計算する必要があります。（ここまで2つ）
• log(4) は log(2) + log(2) で表せるため、既知の値を再利用すれば新たな計算は不要です。
• log(5) は素数なので、新しく計算する必要があります。（ここで3つ）
• log(6) は log(3) + log(2) で求められるため、計算済みの値で十分です。

以上より、必要な対数値は log(2)、log(3)、log(5) の3つということになります。

問題の本質：素数の個数を数える問題への帰着

この問題は、「1からNまでの範囲にある素数の個数を数える」 問題に帰着させることができます。その理由は次のとおりです。

• 素数の場合： これ以上分解できないため、対数値を独立に計算するしかありません。
• 合成数の場合： 必ず素因数分解できるため、素因数の対数値を足し合わせるだけで求められます。

したがって、求めるべき最小のログ値の数は、1からNまでの素数の総数と等しくなります。

C++による実装例

以下のコードでは、エラトステネスの篩（ふるい） を使って効率的に素数判定を行い、1からNまでの素数の個数をカウントしています。

#include<iostream>
#include<vector>
#define MAX 1000005
using namespace std;
vector<int> prime(MAX, 1);

// エラトステネスの篩で素数表を作成する
void seive(int N) {
    prime[0] = prime[1] = 0;
    for (int i = 2; i <= N; i++) {
        if (prime[i] == 1) {
            for (int j = 2; i * j <= N; j++)
                prime[i * j] = 0;
        }
    }
}

// 1からNまでに必要なログ値の最小数（＝素数の個数）を返す
int numberOfLogs(int N) {
    int log_count = 0;
    seive(N);
    for (int i = 1; i <= N; i++) {
        if (prime[i] == 1)
            log_count++;
    }
    return log_count;
}

int main() {
    int N = 8;
    cout<<"Minimum number of log counts required: " << numberOfLogs(N)<<endl;
}

実行結果

Minimum number of log counts required: 4

N = 8 の場合、1から8までの間に存在する素数は 2、3、5、7 の4つです。これら以外の数（4、6、8）は素因数分解によって既知の対数値から導出できるため、結局必要なログ値は4つとなります。

計算量について

エラトステネスの篩による素数列挙の時間計算量は O(N log log N)、空間計算量は O(N) です。Nが大きい場合でも高速に動作するため、この手法は非常に効率的です。