Ce tamis est-il vraiment O (n)?

Question

Quelqu'un peut-il s'il vous plaît me dire comment cela fonctionne dans 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] ; 
     } 
    } 
} 

Je pense que la boucle extérieure sera capable de O (n) du temps et de boucle interne se déroulera O (nombre de nombres premiers inférieur à N) dans le cas où des nombres premiers et O (1) dans le cas où de composite. Mais dans l'ensemble, il doit s'agir de O (n) * O (nombre de nombres premiers inférieur à n). Est-ce que je manque quelque chose?

Merci d'avance.

Answer 1

L'idée clé est que chaque entier compris entre 2 et n est rencontré exactement une fois dans le calcul SPF, donc le nombre total d'itérations de la boucle la plus interne est O (n).

La boucle la plus interne remplit la matrice SPF qui indique le plus petit facteur premier, pour chaque entier compris entre 2 et n.

En effet, pour calculer la matrice SPF, chaque entier k entre 2 et n est représenté comme k = i*prime[j], où prime[j] est un nombre premier en dessous de tous les facteurs premiers de i (ce qui est assuré par la condition prime[j] <= SPF[i] ce qui casserait la boucle autrement). Cela signifie que prime[j] est le plus petit facteur premier de k. Mais cette représentation est unique pour chaque k (le même k ne sera pas rencontré une nouvelle fois, comme un autre k = i2 * prime[j2] factorisation, parce que si prime[j2] n'est pas égal à prime[j] alors l'un d'entre eux ne serait pas le plus petit facteur premier de k). Ainsi, chaque numéro k entre 2 et n apparaît exactement une fois comme le produit i*prime[j], calculé dans la boucle la plus interne.