计数质数

题目形容：统计所有小于非负整数 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));    }}
【每日寄语】 想要失去世界最美妙的货色，那就先让世界看看最美妙的你。愿你遇见更好的本人！