im not able to understand why you have initatiated the loop by i2 please make me clear out the reason behind this …….and how complexity is reduced by initaaizing the loop by i2 .
Sieve of eratothenes
Suppose you are iterating ith index and your jth variable is going to start from ii , but if think why we leaved the other numbers less than ii ( i mean we should start j with 2j right?) but no, actually all the number between 2j and less than ii will already been computed by the index less than i
for example
you cancel all the factors of 2 to 0
for(int i=4;i<=Max;i+=2) p[i]=0
And now you are iteraing from 3
for(int i=3;ii<=Max;i+=2)
if(p[i])
for(int j=ii;j<=Max;j+=2i)
// Here numbers between 2j and ii are 6,7,8 And 6 and 8 are already been computed by iterating for 2 , and we leaved 7 as it is prime .
// Similarly when you see this for a particular index i , you will understand how the sieve is working
// Tha’s why this makes easy to pre-compute all the prime factors less than 10^6 in one go
Hope you understood now !!!