Count the number of prime numbers less than a given non-negative number

Example:

Input: n = 30
Output: 10
Explanation: There are 30 prime numbers less than 10, they are 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29.

Approach: Using Sieve of Eratosthenes algorithm.  Here is how it works:

1. Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).
2. Initially, let p equal 2, the smallest prime number.
3. Enumerate the multiples of p by counting in increments of p from 2p to n, and mark them in the list (these will be 2p, 3p, 4p, ...; the p itself should not be marked).
4. Find the smallest number in the list greater than p that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.
5. When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.

(Image Source: Wiki)

We can optimize it a little bit by modifying step 3. Instead of starting from 2p, we will start from p*p that means now the series will be p*p, p(p + 1), p(p + 2) ... < n. Here we are using the rule that if we want to check if a number is prime or not, we just check that till its square root. 

Implementation in C#:

        public static int CountPrimes(int n)

        {

            bool[] primes = Enumerable.Repeat(true, n + 1).ToArray();

            for (int pIndex = 2; pIndex * pIndex <= n; ++pIndex)

            {

                if (primes[pIndex])

                {

                    for (int i = pIndex * pIndex; i <= n; i += pIndex)

                    {

                        primes[i] = false;

                    }

                }

            }

            int count = 0;

            for (int pIndex = 2; pIndex < n; ++pIndex)

            {

                count = primes[pIndex] ? count + 1 : count;

            }

            return count;

        }

Complexity: O(nlog(logn))