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

user_13151788 0
Viewed 122
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?

sieve-of-eratosthenes primes
1 Answers

If we've already marked the entry corresponding to 3*5 there's no point in marking the entry corresponding to 5*3.

So we start from 5*5 -- just as we've started from 3*3 before that, and indeed have marked the 3*5 = 3*3+3+3 entry then in the process of looping for i=3.

Generalizing this argument gives you the answer to your question.

user_8498910
Related