0204. Count Primes

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

Description

Given an integer n, return the number of prime numbers that are strictly less than n.

Example 1:

**Input:** n = 10
**Output:** 4
**Explanation:** There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Example 2:

**Input:** n = 0
**Output:** 0

Example 3:

**Input:** n = 1
**Output:** 0

Constraints:

• 0 <= n <= 5 * 106

ac1: simple

it's all about math

class Solution {
    public int countPrimes(int n) {
        // edge cases
        if (n <= 2) return 0;

        List<Integer> list = new ArrayList<Integer>();
        list.add(2);

        for (int i = 3; i < n; i++) {
            if (isPrime(i, list)) list.add(i);
        }

        return list.size();
    }
    private boolean isPrime(int n, List<Integer> list) {
        double sqrt = Math.sqrt(n);
        for (int i = 0; i < list.size(); i++) {
            int curr = list.get(i);
            if (curr > sqrt) break;  // greater than square root, no need to check
            if (n % curr == 0) return false;
        }
        return true;
    }
}

// 2 3 5 7 9 11 13 17 19 23 29 ...   1 is not prime number