Count Primes
Description:
Count the number of prime numbers less than a non-negative number, n
References:
由于一个合数总是可以分解成若干个质数的乘积，那么如果把质数（最初只知道2是质数）的倍数都去掉，那么剩下的就是质数了。
public class Solution { public int countPrimes(int n) { boolean[] A = new boolean[n+1]; for(int i=2;i*i<n;i++) { if(!A[i]) { int j = 0; while(i*i+j<=n) { A[i*i+j] = true; j = j+i; } } } int count = 0; for(int j=2;j<n;j++) { if(!A[j]) count++; } return count; } }