How does inner loop at 14:28 runs only for primes.i am not understanding the time complexity after last updation

#1

how does inner loop at 14:28 runs only for primes.i am not understanding the time complexity after last updation

#2

Hi @shakul, the inner loop falls inside an if block which is:

if ( prime[i]==1 )

In the sieve we are created, if an index stores 0, we treat that index as a non-prime and if that index stores value 1 we treat it as a prime. Initially all values are 1 (except 0,1) which indicates that all numbers are prime ; ; until now, for us.
Now when we reach any prime number that is:

if ( prime[i]==1 )

the condition gets true and flow of control moves inside this block and next it encounters our 2nd for loop where we mark 0 at all indices for all multiples of that number.

Let’s consider the seive is this initially:

indices ->           0     1     2     3     4     5     6     7     8     9
values - >           0     0     1     1     1     1     1     1     1     1

now when i=2, that is i is prime, all its multiples are marked as 0, so seive becomes:

indices ->           0     1     2     3     4     5     6     7     8     9
values - >           0     0     1     1     0     1     0     1     0     1

now when i=3 is encountered, its’ val is 1 which means that its is a prime number and now mark all its multiples 0, regardless of whatever they are alrerady, marked 0 or 1 :

indices ->           0     1     2     3     4     5     6     7     8     9
values - >           0     0     1     1     0     1     0     1     0     0

Next value of i is 4, but prime[i] is not = to 1 no the if condition results into a false and hence the second for loop will’nt execute. That’s how we know that the inner/2nd loop will get executed only for prime numbers.

Hope this helps :slight_smile: