Leetcode[204] Count Primes

###Task1 Let’s start with a isPrime function. To determine if a number is prime, we need to check if it is not divisible by any number less than n. The runtime complexity of isPrime function would be O(n) and hence counting the total prime numbers up to n would be O(n2). Could we do better?

We start off with a table of n numbers. Let’s look at the first number, 2. We know all multiples of 2 must not be primes, so we mark them off as non-primes. Then we look at the next number, 3. Similarly, all multiples of 3 such as 3 × 2 = 6, 3 × 3 = 9, … must not be primes, so we mark them off as well. Now we look at the next number, 4, which was already marked off. What does this tell you? Should you mark off all multiples of 4 as well?

###Python

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        isPrime = [True] * max(2, n)
        isPrime[0], isPrime[1] = False, False
        x = 2
        while x * x < n:
            if isPrime[x]:
                for j in range(x + x, n, x):
                    isPrime[j] = False
            x += 1
        return sum(isPrime)
        

###Java

public class Solution {
    public int countPrimes(int n) {
        if (n < 3) {
            return 0;
        }
        boolean[] isPrm = new boolean[n];
        for (int i = 2; i < n; i++) {
            isPrm[i] = true;
        }
        for (int i = 2; i < n; i++) {
            if (isPrm[i]) {
                int parser = i + i;
                while (parser < n) {
                    isPrm[parser] = false;
                    parser = parser + i;
                }
            }
        }
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrm[i]) {
                count++;
            }
        }
        
        return count;
    }
}

###Points

2 × 6 = 12 3 × 4 = 12 4 × 3 = 12 6 × 2 = 12 As you can see, calculations of 4 × 3 and 6 × 2 are not necessary. Therefore, we only need to consider factors up to √n because, if n is divisible by some number p, then n = p × q and since p ≤ q, we could derive that p ≤ √n.