Count the number of prime numbers less than a non-negative number, n. ~~~ public class Solution { public int countPrimes(int n) { //2,3,5,7,11,13,17 //20 5 //init check n boolean[] a = new boolean[n]; for(int i=2; i*i<n; i++) { if(!a[i]) { for(int j=i; i*j<n; j++) { a[i*j] = true; } } } int c=0; for(int i=2; i<n; i++) { if(a[i] == false) ++c; } return c; } } //素数不能被比它小的整数整除, 建一个boolean 数组, 从2开始, 把其倍数小于N的都删掉. //注意 inner loop从i开始, 比i小的会在以前就被check过. ~~~