Ist dieses Sieb wirklich O (n)?

Question

Kann mir bitte jemand sagen, wie das in O (n) funktioniert.

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] ; 
     } 
    } 
} 

denke ich, die äußere Schleife O läuft (n) Zeit und die innere Schleife wird O (Anzahl der Primzahlen kleiner als N) bei der Primzahlen und O (1) im Falle laufen aus Komposit. Aber insgesamt sollte O (n) * O (Anzahl der Primzahlen weniger als n) sein. Fehle ich etwas?

Vielen Dank im Voraus.

Answer 1

Die Schlüsselidee ist, dass jede ganze Zahl zwischen 2 und n genau einmal in der SPF-Berechnung auftritt, also die Gesamtzahl der Iterationen der innersten Schleife ist O (n).

Die innerste Schleife füllt das SPF-Array, das den kleinsten Primfaktor für jede ganze Zahl zwischen 2 und n angibt.

der Tat die SPF-Array zu berechnen, wobei jede ganze Zahl k zwischen 2 und n als k = i*prime[j] dargestellt, wobei prime[j] eine Primzahl unterhalb aller Primfaktoren von ist i (dies wird durch die prime[j] <= SPF[i] Zustand gewährleistet ist was würde die Schleife sonst brechen). Dies bedeutet, dass prime[j] der kleinste Primfaktor von k ist. Aber diese Darstellung ist einzigartig für jede k (dh die gleiche k nicht wieder angetroffen werden, als eine andere k = i2 * prime[j2] Faktorisierung, denn wenn prime[j2] nicht gleich prime[j] ist dann einer von ihnen nicht die kleinste Primfaktor sein k). Somit erscheint jede Zahl k zwischen 2 und n genau einmal als das Produkt i*prime[j], berechnet in der innersten Schleife.