CODEWITHSUNDEEP
primessieve-of-eratosthenes
Roman
Roman

Reputation: 21

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?

Upvotes: 2

Views: 338

Answers (2)

user22425400
user22425400

Reputation: 11

Taking i as the current prime number, its multiples up to i*i can be written as:

i*(i-1)
i*(i-2)
 ⋮
i*(2)

They include divisors less than i and these divisor were already considered in previous loops. For example, i*(2) has already been crossed off (marked False) as multiple of number 2, i*(7) as multiple of number 7, and i*(i-1) as multiple of number i-1. So there is no need to cross off those numbers again and jsut start from i*i.

Upvotes: 1

Will Ness
Will Ness

Reputation: 71099

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.

Upvotes: 2

Related Questions