Description:
Count the number of prime numbers less than a non-negative number, n
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.
求n以内的所有素数，以前看过的一道题目，通过将所有非素数标记出来，再找出素数，代码如下：
1 public int countPrimes(int n) { 2 if (n == 0 || n == 1 || n == 2) 3 return 0; 4 int[] flag = new int[n]; 5 for (int i = 2; i < Math.sqrt(flag.length); i++) { 6 if (flag[i] == 0) 7 for (int j = i; i * j < flag.length; j++) { 8 flag[i * j] = 1; 9 } 10 } 11 int count = 0; 12 for (int i = 2; i < flag.length; i++) 13 count += flag[i]; 14 BitSet bs = new BitSet(); 15 bs.ne 16 return flag.length - count - 2; 17 }
值得注意的是外循环只需要到根号n即可，因为内循环是从i*j即i平方开始的。在LeetCode如果没加根号会产生溢出