Leetcode-204-计数质数

题目描述

• 统计所有小于非负整数 n 的质数的数量。

示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：0


提示：
0 <= n <= 5 * 106

方法一：枚举

• 很直观的思路是我们枚举每个数判断其是不是质数。

• 考虑质数的定义：在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。

• 因此对于每个数 x，我们可以从小到大枚举[2,x-1]中的每个数 y，判断 y 是否为 x 的因数。但这样判断一个数是否为质数的时间复杂度最差情况下会到 O(n)，无法通过所有测试数据。

注意：

举例子 ：

• x = 6 y = 2 x/y =3
• min(y,x/y)= 2

public class MainClass {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        // 初始化数据
        String line;

        while ((line = in.readLine()) != null){
            int n = Integer.parseInt(line);
            int ret = new Solution().countPrimes(n);
            String out = String.valueOf(ret);
            System.out.println(out);
        }
    }
}

class Solution{
    public int countPrimes(int n) {
        int ans = 0;
        // O(n)
        for(int i = 2;i < n;++i){
            ans += isPrime(i)?1:0;
        }
        return ans;
    }

    // O(sqrt(n))
    public boolean isPrime(int x){
        for(int i = 2;i*i <= x;++i){
            if(x % i == 0){
                return false;
            }
        }
        return true;
    }
}

方法二 ： 埃氏筛

• 枚举没有考虑到数与数的关联性，因此难以再继续优化时间复杂度。接下来我们介绍一个常见的算法，该算法由希腊数学家厄拉多塞（Eratosthenes）提出，称为厄拉多塞筛法，简称埃氏筛。

注意：

class Solution {
    public int countPrimes(int n) {
        // 1. 初始化质数数组
        int[] isPrime = new int[n];
        Arrays.fill(isPrime,1);

        // 2. 进行统计
        int ans = 0;
        for(int i = 2;i < n;++i){
            if (isPrime[i] == 1){   // 如果遇到的这个数是质数的话,开始判断,否则不会进循环
                ans += 1;           // 遍历数组,如果是质数的话,那么给结果加1
                if((long)i*i < n){  // 如果i是质数 那么i*i就是合数 起始位置：需要标记为0
                    for(int j = i*i;j < n;j += i){  // 同时,从i*i 位置开始标记,
                        isPrime[j] = 0;             // 标记i*i + i也同时为i的倍数，只要是i的倍数,那么就一定不是质数
                    }
                }
            }
        }
        return ans;
    }
}

打赏