エラトステネスの篩の計算量

　蟻本には、エラトステネスの篩の計算量はO(n log log n) と書いてあります。
log log nってなんぞや？どこから出てきたの？とずっと疑問でしたが、何故こうなるか分かったのでメモしておきます。

エラトステネスの篩のコード

C++で書く場合は、概ね以下のようなコードが一般的かと思います。

bool isPrime[N];

int main() {
    for (int i = 2; i < N; i++)
        isPrime[i] = true;

    for (int i = 2; i < N; i++) {
        if (!isPrime[i]) continue;
        for (int j = 2 * i; j < N; j += i)
            isPrime[j] = false;
    }
}

計算量の見積もり

まず簡単のため、上のソースの”素数でないなら飛ばす”という処理（※）が無かった場合を考えてみます。
（※）if (!isPrime[i] ... ) の行のこと。

二重ループのところが一番重い処理で、計算量は、

∑_{ i < N} N / i = N * ∑_{i < N} 1 / i = N ln (N)

となります。ここまでは簡単です。

次に、”素数でないなら飛ばす”がある場合を考えてみます。
計算量は、

∑_{ p < N, p is prime} N / p = N * ∑_{p < N, p is prime} 1/p

となりますが、∑_{p < N, p is prime} 1/pがもしやln ln(N)になるのでは？と予想をつけてみたのです。実験してみたところ、以下のようになりました。

N	∑_{p < N, p is prime} 1/p	ln ln N
1e6	2.887	2.626
1e7	3.041	2.780
1e8	3.175	2.913

両者の値はnearly equalであることが分かりました。ということで、
∑_{p < N, p is prime} 1/p = ln ln(N)
が漸近的に成り立つのではないか？そうであれば、エラトステネスの篩の計算量がO(N log log (N))というのも納得できるのだが。。
と思い調べていると、以下の情報を見つけました。

Euler then concluded
1/2 + 1/3 + 1/5 + 1/7 + 1/11 ..... = ln ln (+∞)

It is almost certain that Euler meant that the sum of the reciprocals of the primes less than n is asymptotic to ln(ln(n)) as n approaches infinity. It turns out this is indeed the case.

-- Divergence of the sum of the reciprocals of the primes - Wikipedia, the free encyclopedia

ということで、予想は正しかったみたいです。