# Leetcode 204. Count Primes

xiaoxiao2021-03-26  5

public class Solution { public int countPrimes(int n) { int cnt = 0; boolean[] prime = new boolean[n]; for (int i=2; i*i<=n; i++) for (int j=2; i*j<n; j++) prime[i*j] = true; for (int k=2; k<n; k++) if (!prime[k]) cnt++; return cnt; } }

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; } }