LeetCode-204-计数质数

计数质数

题目描述:统计所有小于非负整数 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));
    }
}
【每日寄语】 想要得到世界最美好的东西,那就先让世界看看最美好的你。愿你遇见更好的自己!

你可能感兴趣的