Count the number of prime numbers less than a non-negative number, n.
Example:
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-primes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
给出一个正整数n，求（0，n）范围内质数的个数。这道题可以很直观的采用暴力解法，设一个计数器result，当0<= n <= 2时，result肯定为零，因为0 ，1都不是质数。所以只需要从n >= 3的时候开始考虑，故result可初始化为1，因为2是质数。遍历[3，n），当遇到一个质数时，计数器加1，直到返回最终结果。初步暴力解法代码如下：
class Solution { public int countPrimes(int n) { if(n <=2) { return 0; } int result = 1; for(int i = 3; i < n; i++) { if(isPrimes(i)) { result++; } } return result; } public boolean isPrimes(int m) { for(int i = 2; i <= m/2; i++) { if(m % i == 0) { return false; } } return true; } }
这个解法很直观，也无疑是可以求出正确答案的。然而就是效率太低了，因为重复计算了很多不必要的数，而且也不断调用isPrime（int n）这个函数，对时间的损耗实在太大。因此可以在这个基础上作一个小小的优化。
在求一个数m是否是质数时，只需要求出在[2， Math.pow(m,0.5)]这个范围内是否存在一个或以上的数，可以整除m，所以可以把[0,m/2]的范围缩减一下。其次，由于除了0和2以外，所有的偶数都可以被2整除，所以可以排除[3,n）内的所有偶数。还有一个可优化的点就是isPrime（int n）这个函数。由于调用函数的时间较长，因此我们可以把这个函数简化到用数条语句来代替。优化过的代码如下：、
class Solution { public int countPrimes(int n) { if(n <=2) { return 0; } int result = 1; for(int i = 3; i < n; i++) { if(i % 2 == 0) { continue; } boolean isPrime = true; for(int j = 3; j * j <= i; j += 2) { if(i % j == 0) { isPrime = false; break; } } if(isPrime == true) { result++; } } return result; } }
原文：https://www.cnblogs.com/WakingShaw/p/11986313.html