Почему сложность (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 штрихами получить более редки, как числа становятся больше, поэтому плотность в п приблизительно п (п). Таким образом, один из способов приблизиться к вашей проблеме - превратить ее в интеграл, где вы хотите, чтобы интеграл от x = 1 до x = n от 1/(x ln (x)). Я думаю, что производная от ln (ln (x)) равна (1/ln (x)) * (1/x) = 1/(x ln (x)), поэтому я считаю, что если это приближение справедливо, интеграл идет чтобы быть O (ln (ln (n)) - который получает ответ, который вы ищете.