The optimization tricks for determining if a number is Prime:
1. Check all n's factors from 2 to n - 1
2. Check until n/2, because n must not be divisible by the number greater than n/2
3. Check until sqrt(n). Because if n is dividible by some number p, then n = p * q, since p <= q, so p is up to sqrt(n).
So the time complexity is O(sqrt(n)) to determine if a number is prime.
The optimization tricks for count the number of primes less than n
1. If the current number is p, we only need to start from p^2, because 2*p, 3*p, 4*p, ..., has already been marked off. So we start from p^2, and p^2 + p, p^2 + 2p, ...
2. we terminate the loop condition at sqrt(n), because all non-primes >= sqrt(n) must have already been marked off.