204. Count Primes

Question

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

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Thinking:

• Method：TLE
  • 合数是奇数的乘积，将所有的已知的质数加入集合，然后每次遍历。

class Solution {
    public int countPrimes(int n) {
        if(n < 2) return 0;
        if(n == 2) return 1;
        int count = 1;
        Set<Integer> set = new HashSet<>();
        set.add(2);
        for(int i = 3; i < n; i+=2){
            if(isPrime(i, set)) count++;
        }
        return count;
    }
    private boolean isPrime(int n, Set<Integer> set){
        for(Integer num : set){
            if(n % num == 0) return false;
        }
        set.add(n);
        return true;
    }
}

• Method 2:
  • 通过一个布尔型数组存储数字是否是质数
  • 每当我们发现一个质数，我们就用该数字乘以其后的所有数字，直到两数之积大于n。

class Solution {
    public int countPrimes(int n) {
        boolean[] notPrime = new boolean[n];
        int count = 0;
        for(int i= 2; i < n; i++){
            if(!notPrime[i]){
                count++;
                for(int j = 2; i * j < n; j++)
                    notPrime[i * j] = true;
            }
        }
        return count;
    }
}

二刷

1. 如何发现合数分析。
2. 合数一定是质数的乘积。8 = 2 * 4 = 2 * 2 * 2
3. 所以当我们发现了一个质数时，我们从头开始遍历所有的质数到当前质数的乘积，这些乘积一定是合数。

   class Solution {
    public int countPrimes(int n) {
        boolean[] notPrime = new boolean[n];
        int count = 0;
        for(int i = 2; i < n; i++){
            if(!notPrime[i]){
                count++;
                for(int j = 2; j * i < n; j++){
                    notPrime[j * i] = true;
                }
            }
        }
        return count;
    }
   }
   

Amazon session

class Solution {
    public int countPrimes(int n) {
        boolean[] notPrime = new boolean[n];
        int count = 0;
        for(int i = 2; i < n; i++){
            if(!notPrime[i]){   // if current value is prime.
                count++;
                for(int j = 2; i * j < n; j++){ // change all multiples of i to not prime.
                    notPrime[i * j] = true;
                }
            }
        }
        return count;
    }
}