static int countPrimes(int n) {
		if (n <= 2) return 0;
		boolean [] primes = new boolean[n];
		for (int i = 2; i < n; i++) {
			primes[i] = true;
		}
		
		for (int i = 2; i * i < n; i++) {
			if (primes[i]) {
				// primes[i + i * ii] already marked,ii = 2, ... i - 1, so we start with i * i
				// for example, when i = 2, we mark 2 * 3, 2 * 4...
				// so when i = 3, we don't need to mark 3 * 2 = (3 + 3)
				for (int j = i * i; j < n; j += i) {
					primes[j] = false;
				}
			}
		}
		
		int count = 0;
		for (int i = 2; i < n; i++) {
			if (primes[i]) count++;
		}
		
		return count;
	}