public class CountPrimes {
	public int countPrimes(int n) {
		if (n < 2)
			return 0;
		int count = 0;
		for (int i = 2; i < n; i++)
			if (isPrime(i))
				count++;
		return count;
	}

	private boolean isPrime(int k) {
		if (k == 2)
			return true;
		if (k % 2 == 0)
			return false;
		// Only need to check odd numbers from 3 to sqrt(num)
		for (int i = 3; i * i <= k; i += 2) {
			if (k % i == 0)
				return false;
		}
		return true;
	}
}
