algorithm - 为什么 (1/2 + 1/3 + 1/5 + ...) = loglogN 的复杂度？

Question

N * (½ + ⅓ + ⅕ + … ) = O(NloglogN)

为什么 (1/2 + 1/3 + 1/5 + ...) = loglogN 的复杂度？我不明白

代码如下:

void sieve(int N) {
    bool isPrime[N+1];
    for(int i = 0; i <= N;++i) {
        isPrime[i] = true;
    }
    isPrime[0] = false;
    isPrime[1] = false;
    for(int i = 2; i * i <= N; ++i) {
         if(isPrime[i] == true) {
             // Mark all the multiples of i as composite numbers
             for(int j = i * i; j <= N ;j += i)
                 isPrime[j] = false;
        }
    }
}

Answer 1

根据 https://en.wikipedia.org/wiki/Prime_number_theorem随着数字变大，素数变得越来越稀少，因此 n 处的密度大约为 ln(n)。因此，粗略近似您的问题的一种方法是将其转化为积分，其中您希望从 x=1 到 x=n 的积分为 1/(x ln(x))。我认为 ln(ln(x)) 的导数是 (1/ln(x))*(1/x) = 1/(x ln(x)) 所以我认为如果这个近似值是有效的积分为 O(ln(ln(n)) - 得到您正在寻找的答案。