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?