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?
https://stackoverflow.com/questions/5811151/why-do-we-check-up-to-the-square-root-of-a-prime-number-to-determine-if-it-is-pr
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.
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