I_lOVE_ROMAN's blog

Sieve of Eratosthenes

By I_lOVE_ROMAN, history, 3 years ago, In English

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?

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it
???
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have gotten the answer of this link?But my question is not that.I am asking why the 2nd loop starting from i*i.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      consider a prime i = 7 , then all multiples of i=7 (lesser then i*i) are already marked,

      7*2 (marked by 2)

      7*3 (marked by 3)

      7*4 (marked by 2)

      7*5 (marked by 5)

      7*6 (first marked by 2)

      7*7 (still unmarked)

      so better start from square of a prime number

      → Reply