I didn’t read the blog yet, but here is the related answer of your queries:

- Why in sieve algo, the loop goes up to sqrt(n) instead of n:

Ans: According to prime number def. They are those number which can be divisible by both 1 and themselves only. So the possibility that a number can be divisible is only up to sqrt(n).

Basically, we are gonna check up to N/2 to prove our statement.

Let’s proof this by example:

```
N = 9
sqrt(9) = 3
```

9 can be divisible by a number greater than 3 but covered in selected range(2,3)

```
N = 25
sqrt(25) = 5
```

25 can be divisible by a number greater than 5, but they are already covered in range(2,3,5)

**EDIT:**

```
N = 36
sqrt(36) = 6
```

It include numbers 2,3,5

2 - (4,6,8,10,12,14,16,18…) covered all this number

3 - (6,9,12,15,…)

5 - (10,15,20,…)

Let’s take 7 which is greater than 6

7-(14,21,…)

but these numbers are already covered, that’s why we take sqrt(n) instead of going to N or N/2.