leetcode Question: Count Primes

Count Primes

Description:

Count the number of prime numbers less than a non-negative number, n.

Analysis:

This is a classic algorithm question.  Here I'd like to introduce one of the famous algorithm called "Sieve of Eratosthenes." The general idea is to use a "sieve", to filter the numbers form 2 to n, each time, we get the next prime number in the array, and remove the multiples of this prime number. Iterating this process until the square of next prime number is greater than the last number n.  The numbers now left in the array are all primes.

In this problem, just be careful that the last number is not included.

According to the literature, the time complexity of this algorithm is nloglogn. Details of the analysis can be found in the wikipedia page here.

Code(C++):

class Solution {
public:
    int countPrimes(int n) {
        vector<bool> num(n,true);
        int i = 2;
        while (i * i < n){
            for (int j = 2; j*i < n; j++){
                num[j*i] = false;
            }
            
            i++;
            
            while (num[i] == false && i*i < n){
                i++;
            }
        }
        int res=0;
        for (int i=2;i<n;i++){
            if (num[i] == true){
                res ++;
            }
        }
        return res;
    }
};

Code(Python):

class Solution:
    # @param {integer} n
    # @return {integer}
    def countPrimes(self, n):
        num=[1 for x in range(n)] 
        i = 2
        while i * i < n:
            j = 2
            while j*i < n:
                num[j*i] = 0
                j += 1
            i += 1
            while num[i] == 0 and i * i < n:
                i += 1
                
        return sum(num[2::])