Live long and prosper
Description:
Count the number of prime numbers less than a non-negative number, n.
12345678910111213141516171819
public class Solution { public int countPrimes(int n) { boolean[] notPrime = new boolean[n]; for (int i = 2; i * i < n; i++) { if (notPrime[i] == false) { for (int j = i * i; j < n; j += i) { notPrime[j] = true; } } } int count = 0; for (int i = 2; i < n; i++) { if (notPrime[i] == false) { count++; } } return count; }}