204:Count Primers

target:Count the number of PRime numbers less than a non-negative number n

我第一次编写的解决代码，时间复杂度是O（n2）,在40多万时就挂了。

	//O(n2),cost too much time	public int simplecountPrimes(int n) {		int num = 0;		for (int i = 2; i < n; i++) {			boolean flag = isPrimer(i);			if(flag == true){				num++;			}		}		return num;	  }	public boolean isPrimer(int m){		boolean flag = true;		for (int i = 2; i < m; i++) {			int remainder = m%i;			if(remainder==0){				flag = false;				break;			}		}		return flag;	}
这里着重介绍埃拉托斯特尼筛法（Sieve of Eratosthenes）：
核心思想：逐个遍历数字，数字的倍数必然不是素数，直接去除。
p * q = n; 当p大于q之后，内容出现重复，故我们只需要思考p <√n的开方内的数字的遍历。
同样的根据上面这行思想，当我们对√n以下数字遍历时，我们考虑的倍数的起点一定是i * i （此时正在遍历的数字）
	//Sieve of Eratosthenes, O(nlglgn)	public int countPrimers(int n){		int num = 0;		boolean[] isPrimers = new boolean[n];		for (int i = 0; i < isPrimers.length; i++) {			isPrimers[i] = true;		}		for (int i = 2; i*i < n; i++) {			if(!isPrimers[i]){				continue;			}			for(int j = i*i;j < n ;j += i){				isPrimers[j] = false;			}		}		for (int i = 2; i < n; i++) {			if(isPrimers[i] == true){				num++;			}		}		return num;	}