This is an elegant algorithm. Some question regarding the implementation one should be able to answer:
Why the limit is sqrt(n+1.) + 2
We can use proof by contradiction
Why do we mark the numbers greater than i*i
The numbers have already been marked
Further Optimisation:
Memory Efficient Sieve: We don’t need to memory for all the numbers multiple of 2 for mark except 2. And the mark[] array will have two value 0/1. So we can use the 32 bit and further optimise. See Yarin's Sieve
Segmented Sieve: We have found all the Prime numbers between 0 to n. But there could be a problem where we have to find the prime between a and b.