Sieve of Eratosthenes

Revision en1, by 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?

Tags #number theory, #eratosthenes_sieve

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English I_lOVE_ROMAN 2021-07-16 20:49:20 568 Initial revision (published)