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)
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
but these numbers are already covered, that’s why we take sqrt(n) instead of going to N or N/2.