204. Count Primes

Posted on | Edited on | Views:

https://leetcode.com/problems/count-primes/

Check if number is prime number\
Naive solution: execution time (619 ms)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    private boolean checkPrime(int n){
        if(n<2) return false;
        if(n==2) return true;
        if(n%2==0) return false;
        for(int i=3;i<=(int)Math.sqrt(n);i+=2){
            if(n%i==0) return false;
        }
        return true;
    }
    public int countPrimes(int n) {
        int cnt=0;
        for(int i=2;i<n;i++){
            if(checkPrime(i)) cnt++;
        }
        return cnt;
    }
}

Finding Prime numbers - Sieve of Eratosthenes\
youtube

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int countPrimes(int n) {
        if (n <= 1) return 0;

        boolean[] prime = new boolean[n + 1];
        for (int i = 2; i <= n; i++) prime[i] = true;

        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (prime[i]) {
                for (int j = 2; j * i <= n; j++) {
                    prime[i * j] = false;
                }
            }
        }

        int count = 0;
        for (int i = 2; i < n; i++) {
            if (prime[i]) count++;
        }
        return count;
    }
}

0%