このふるいは本当にO（n）ですか？

Question

誰でもこのことがO（n）でどのように機能しているか教えてください。

http://www.geeksforgeeks.org/sieve-eratosthenes-0n-time-complexity/

void manipulated_seive(int N) 
{ 
    // 0 and 1 are not prime 
    isprime[0] = isprime[1] = false ; 

    // Fill rest of the entries 
    for (long long int i=2; i<N ; i++) 
    { 
     // If isPrime[i] == True then i is 
     // prime number 
     if (isprime[i]) 
     { 
      // put i into prime[] vector 
      prime.push_back(i); 

      // A prime number is its own smallest 
      // prime factor 
      SPF[i] = i; 
     } 

     // Remove all multiples of i*prime[j] which are 
     // not prime by making isPrime[i*prime[j]] = false 
     // and put smallest prime factor of i*Prime[j] as prime[j] 
     // [ for exp :let i = 5 , j = 0 , prime[j] = 2 [ i*prime[j] = 10 ] 
     // so smallest prime factor of '10' is '2' that is prime[j] ] 
     // this loop run only one time for number which are not prime 
     for (long long int j=0; 
      j < (int)prime.size() && 
      i*prime[j] < N && prime[j] <= SPF[i]; 
      j++) 
     { 
      isprime[i*prime[j]]=false; 

      // put smallest prime factor of i*prime[j] 
      SPF[i*prime[j]] = prime[j] ; 
     } 
    } 
} 

Iは、外側のループ時間と内側のループは、ケース（1）素数とOの場合はO（Nより小さい素数の数）を実行します（N）Oを実行すると思いの合成。しかし全体的にO（n）* O（素数の数はn未満）でなければなりません。何か不足していますか？

ありがとうございます。

Answer 1

重要なアイデアは、2とnの間の各整数にSPF計算で1回遭遇することです。したがって、最も内側のループの反復の総数はO（n）です。

最も内側のループは、2とnの間の各整数に対して、最小の素因数を示すSPF配列を塗りつぶします。

実際、SPFアレイを計算するために、2及びNの間の各整数Kはprime[j]がのすべての素因数以下素数であるI（これはprime[j] <= SPF[i]条件によって保証されるk = i*prime[j]、として表されますそれ以外の場合はループを中断する）。つまり、prime[j]は、kの最小の素因数です。しかし、この表現はprime[j2]がprime[j]と等しくないならば、そのうちの一つは、最小の素因数ではないので（すなわち、同じKは、別のk = i2 * prime[j2]因数分解として、再び遭遇されることはありません各Kのためのユニークでありますk）。したがって、各番号kは、2とnの間で、最も内側のループで計算されたi*prime[j]という製品として一度だけ表示されます。