Finding Prime numbers - Sieve of Eratosthenes
O(n^1.5) approach.
public class Solution { public int countPrimes(int n) { int count = 0; for (int i=1; i<n; i++) { if (isPrime(i)) { count++; } } return count; } public boolean isPrime(int num) { if (num == 1) { return false; } if (num == 2) { return true; } // Check if num can be divided by even numbers if (num % 2 == 0) { return false; } // Check if num can be divided by odd numbers // If num can be divided by p, that num = p * q and assume p <= q, // we can derive that p <= num^0.5 b/c (p * q) ^ 0.5 = num ^ 0.5 and p ^ 0.5 <= q ^ 0.5. // So we only need to check all odd numbers from 3 to num^0.5. for (int i=3; i<=Math.sqrt(num); i+=2) { if (num % i == 0) { return false; } } return true; } }