Count Primes
Source code Read on Github
1 public class Solution {
2 public int countPrimes(int n) {
3
4 if(n < 2) return 0;
5
6 BitSet b = new BitSet();
7
8 b.set(0);
9 b.set(1);
10
11 for(int p = 2; p * 2 < n ; p = b.nextClearBit(p + 1)){
12 for(int i = 2; p * i < n ;i++){
13 b.set(p * i);
14 }
15 }
16
17 b.flip(0, n);
18
19 return b.cardinality();
20 }
21 }