leetcode [#204]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

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

---

解决方案

public class Solution {
    public int countPrimes(int n) {
        if(n <= 2) return 0;
        int count = 0;
        boolean[] primeNum = new boolean[n+1];

        for(int k = 2; k <= n; k++) primeNum[k] = true;
        for(int i = 2; i <= Math.sqrt(n); i++){
            if(!primeNum[i]) continue;
            for(int j = i * i; j < n; j += i){
                primeNum[j] = false;
            }
        }
        for(int m = 2; m < n; m++){
            if(primeNum[m]) count++;
        }
        return count;
    }
}

---

注意事项

1. 以下方法复杂度高会超时：

   public class Solution {
       public int countPrimes(int n) {
           if(n <= 2) return 0;
           int count = 0;
           int k = 2;
           while(k < n) {
               if(isPrime(k)) count++;
               k++;
           }
           return count;
       }
       private static boolean isPrime(int m){
           for(int i = 2; i <= Math.sqrt(m); i++) if(m % i == 0) return false;
           return true;
       }
   }

2. 思路是：
   对于给定n,判断小于n的每个正是是质数还是合数，在统计质数个数之和。要提高判断质数/合数的效率：创建一个数组，长度为n+1，数组元素值true/false代表对应下标的数字是质数还是合数，初始化认为每个元素都是true。整个遍历过程是一个标记的过程：标记从2开始小于根号n的所有整数的平方以及从平方开始的各个倍数，这些显然都是合数，且覆盖了全部合数的可能性。