**Special thanks for StefanPochmann's precious advices!**

The basic idea is:

```
Once we find a prime number i, then mark the composite numbers:
i*i, i*i+i, i*i+i*2 .. i*i+i*k < n
```

Hints:

```
1) 1 is not a prime number
2) n is excluded
3) As (i-1)*i is already marked in the previous case of i-1, so we can start from i*i
```

**Time complexity = O(n) + O(overlapped possibilities)** - Detailed Analysis

There're overlapped possibilities: 24=2x12, 3x8, 4x6..so it should be more than O(n). The time complexity is: O(n) + O(overlapped possibilities)

```
public int countPrimes(int n) {
boolean isComposite[] = new boolean[n];// isComposite[i]: If i is a composite number
int count = 0;
for (int i = 2; i < n; i++) {
if (!isComposite[i]) {
count++;
if (i < Math.sqrt(n))
for (int j = i * i; j < n; j += i)
isComposite[j] = true;// Mark j as a composite number
}
}
return count;
}
```