Count Primes

Description:
Count the number of prime numbers less than a non-negative number, n.
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.
Hint:

1. Let's start with a isPrime function. To determine if a number is prime, we need to check if it is not divisible by any number less than n. The runtime complexity of isPrime function would be O(n) and hence counting the total prime numbers up to n would be O(n²). Could we do better?
   
2. As we know the number must not be divisible by any number > n / 2, we can immediately cut the total iterations half by dividing only up to n / 2. Could we still do better?
   
3. Let's write down all of 12's factors:
   

   2 × 6 = 12
   3 × 4 = 12
   4 × 3 = 12
   6 × 2 = 12
   

   As you can see, calculations of 4 × 3 and 6 × 2 are not necessary. Therefore, we only need to consider factors up to √n because, if n is divisible by some number p, then n = p × q and since p ≤ q, we could derive that p ≤ √n.
   Our total runtime has now improved to O(n^1.5), which is slightly better. Is there a faster approach?
   

   public int countPrimes(int n) {
      int count = 0;
      for (int i = 1; i < n; i++) {
         if (isPrime(i)) count++;
      }
      return count;
   }
   
   private boolean isPrime(int num) {
      if (num <= 1) return false;
      // Loop's ending condition is i * i <= num instead of i <= sqrt(num)
      // to avoid repeatedly calling an expensive function sqrt().
      for (int i = 2; i * i <= num; i++) {
         if (num % i == 0) return false;
      }
      return true;
   } 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

public class Solution { public int countPrimes(int n) { boolean isPrime[] = new boolean[n]; if(n<2)return 0; //first of all, assume all numbers are prime for(int i=2;i<n;i++){ isPrime[i]=true; } //then mark the non-prime ones: it can be divided by other numbers other than 1 and itself for(int i=2;i*i<n;i++){ //becuase it is multiply so use i*i instead of i if(isPrime[i]){//since we start from smallest prime, we will have less number to to through the second loop, since all current prime's multiplications will be marked as non-prime //then mark all its multiplies as non prime for(int j=2;j*i<n;j++){ isPrime[j*i]=false; } } } int cnt = 0; for(int i=2;i<n;i++){ if(isPrime[i])cnt++; } return cnt; } }