关于java:LeetCode204计数质数

33次阅读

共计 752 个字符，预计需要花费 2 分钟才能阅读完成。

题目形容：统计所有小于非负整数 n 的质数的数量。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：暴力破解法

遍历从 2 开始到 n - 1 的所有数字，用 result 记录质数的数量，如果是质数，则 result 加 1，判断质数的办法如下：

如果数字是 2 或 3，则间接返回 true；

如果数字大于 3，则从 2 到 num 的平方根，如果以后数 num 能被整除，则阐明这个数不是质数，遍历实现，如果没有能整除的，则阐明这个数是质数。

阐明：该办法效率低，有更优解，待优化。

public class LeetCode_204 {
    /**
     * 暴力破解法：提交后超出工夫限度，性能不好
     * @param n
     * @return
     */
    public static int countPrimes(int n) {
        int result = 0;
        for (int i = 2; i < n; i++) {if (isPrime(i)) {result++;}
        }
        return result;
    }

    public static boolean isPrime(int num) {if (num == 2 || num == 3) {return true;}
        boolean result = true;
        for (int i = 2; i <= Math.sqrt(num); i++) {if (num % i == 0) {return false;}
        }
        return result;
    }

    public static void main(String[] args) {System.out.println(countPrimes(1500000));
    }
}