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