0204. Count Primes - kumaeki/LeetCode GitHub Wiki

0204. Count Primes

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

Example 1:

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

Example 2:

Input: n = 0
Output: 0

Example 3:

Input: n = 1
Output: 0

Constraints:

  • 0 <= n <= 5 * 10^6

解法1

用list来储存从2到n的质数的个数.
果不其然超时.

class Solution {
    
    public int countPrimes(int n) {
        if(n <= 2)
            return 0;
        
        int res = 0;
        List<Integer> list = new ArrayList<Integer>();
        list.add(2);
        
        for(int i = 3; i < n; i+=2){
            
            boolean isPrime = true;
            for(int p: list)
                if(i % p == 0){
                    isPrime = false;
                    break;
                }
            
            if(isPrime)
                list.add(i);
            
        }

        return list.size();
    }
}

解法2

Sieve of Eratosthenes

class Solution {
    
    public int countPrimes(int n) {        
        int res = 0;
        int[] arr = new int[n];
        // 从2到n
        for(int i = 2; i < n; i++)
            arr[i] = i;
        
        for(int i = 2; i < n; i++){
            // 如果i已经被标记过, 那么肯定是合数
            if(arr[i] == 0)
                continue;
            
            // 质数个数加1
            res++;
            
            // 标记所有i的倍数,直到最大
            for(int j = i;j < n; j += i)
                arr[j] = 0;
        }
        
        return res;
    }
}

进一步改进为下面的代码
改进点有两个

  1. 外层的循环i < n 改为 i * i < n, 大量减少循环次数
    以 n = 26为例, 外层循环只需要到5就可以, 因为超过了5的数 如果是合数, 那么必然是一个大于5的数和小于5的数的乘积,(比如20) 而这个数会在之前的循环中被标记到(4 * 5, 在 i = 4的循环中被标记)
  2. 内层的循环 j, 起始点j = i 改成 j = i * i, 大量减少循环次数
    对于任意的i, i * i 之前的合数 1 * i, 2 * i,... (i - 1) * i 都应该在之前的 1 ,2 i-1 的循环中被标记过了.
class Solution {
    
    public int countPrimes(int n) {        
        int res = 0;
        int[] arr = new int[n];
        // 从2到n
        for(int i = 2; i < n; i++)
            arr[i] = i;

        // 改进点1
        // for(int i = 2; i < n; i++){
        for(int i = 2; i * i < n; i++){
            // 如果i已经被标记过, 那么肯定是合数
            if(arr[i] == 0)
                continue;
            
            // 标记所有i的倍数,直到最大
            // 改进点2
            // for(int j = i; j < n; j += i)
            for(int j = i * i; j < n; j += i)
                arr[j] = 0;
        }
        
        for(int val : arr)
            if(val > 0)
                res++;
        
        return res;
    }
}
⚠️ **GitHub.com Fallback** ⚠️