Count the number of prime numbers less than a non-negative number, n.
首先，要找出小于n的质数，也就是要分别判断n-1个数是不是质数。
那么要怎么判断一个数是不是质数？
比如一个数m，是不是要判断从1到m-1能不能被m整除？
那么这样要进行m-1次判断。
优化一下，其实可以只进行根号m次
因为 2*3 和 3*2 是一回事
在这个问题里面，又涉及到判断每一个小于n的数是不是质数
可以用到sieve of eratosthenes
简单地说牺牲空间换时间 每找到一个质数 将其所有倍数全部标记为非质数
这样遍历一次就行
问题又来了，是不是就要全部遍历一遍？
其实也只用到根号n的程度，道理同前，检查到根号n的时候，后半部分的非质数也全部被标记了。
public int countPrimes(int n) { boolean[] isPrime = new boolean[n];//在最先开始的初始化 boolean的默认是false for (int i = 2; i < n; i++) {//从1到n-1 isPrime[i] = true;先都改成质数 1就直接false } for (int i = 2; i * i < n; i++) {//从2检查到根号n if (!isPrime[i]) continue;//被标记了不是质数就跳过去 for (int j = i * i; j < n; j += i) {//当前这个是质数 那么它所有的倍数都要被标记 注意被标记的起点是i*i 因为i*i-1会被i-1标记的 就不重复了 isPrime[j] = false; } } int count = 0; for (int i = 2; i < n; i++) { if (isPrime[i]) count++; } return count; }
