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

A prime number is a number that is only divisible by 1 and itself

Version 1

According to the definition of prime number, we can create
a function isPrime to test if a number n is a prime number:

1
2
3
4
5
6
7
8
9
10
11
boolean isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

Then, we can iterate through all the number between 1 to n for all the
prime numbers. O(n^2)

Version 2

Some of the step in the for-loop in the isPrime is not necessary since
if n is not a prime number, then there must be n = p x q and p <= q,
then p must be less than sqrt(n). We only need to test for p to get
all the information if n is a prime number.

1
2
3
4
5
6
7
8
9
10
11
boolean isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

isPrime(n) is now O(sqrt(n)), total complexity is O(n * sqrt(n))

Version 3

The idea is to build a table boolean[n], mark
all the non-prime numbers from 2 to n and the un-marked is prime numbers.
The reason it is faster is that it uses extra space for dynamic programming.