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過. ~~~