LeetCode-计数质数

2023-07-29 53

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： LeetCode-计数质数

🔎概述

给定整数 n ，返回所有小于非负整数 n 的质数的数量

🔎题解

🌻解法1(朴素解法)

public int countPrimes(int n) {
        int count = 0;
        for (int i = 2; i < n; i++) {
            if(isPrime3(i))
                count++;
        }
        return count;
}
private boolean isPrime(int num) {
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if(num % i == 0) return false;
        }
        return true;
}

对于一个正整数9,我们只需要判断9对于2-9的平方根的数字取余是否为0,即可判断该数是否为质数

对于质数,是指该数是否能仅被1和它本身整除,所以从2开始

为什么是9的平方根,因为任何一个数都不可能分解成两个大于其平方根的数的乘积.肯定只能分解为一个大于或等于其平方根,另一个小于或等于其平方根.

显然,这种方法是不够高效的

下面介绍一种更为高效的方法

🌻解法2(埃氏筛)

public int countPrimes(int n) {
        int count = 0;//统计有多少个质数
        boolean[] notPrime = new boolean[n];//0~n-1
        for (int i = 2; i < n; i++) {
            if(notPrime[i]) {//如果不是质数,继续
                continue;
            }
            count++;//是质数,个数+1
            //这里用long因为题目给的数据范围是10^6,过大
            //从2开始,j = i * i,即为i的最小倍数,那么i的倍数一定不是质数
            //j += i,表示在i的最小倍数再加上i
            //j = 4,j += i(j = 6,8,10...),这些数字均不是质数
            for (long j = (long)i * i; j < n; j += i) {
                notPrime[(int)j] = true;
            }
        }
        return count;
}