Sieve of Eratosthenes

Правка en1, от I_lOVE_ROMAN, 2021-07-16 20:49:20

Why second loop of sieve of Eratosthenes starting from square of current prime number?

vector<bool>vc(100006,1);
void seive(int n)
{
    vc[0]=vc[1]=0;
    int i,j;
    for(i=2;i*i<=n;i++)
    {
        if(vc[i]==1)
        {
            for(j=i*i;j<=n;j=j+i)
            {
                vc[j]=0;
            }
        }
    }

}

My question is why the second loop starting from square of i. How the multiples before the square of current prime(i) getting marked ?Actually how are we so sure of it?

Теги #number theory, #eratosthenes_sieve

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский I_lOVE_ROMAN 2021-07-16 20:49:20 568 Initial revision (published)