204_Count Primes

Count the number of prime numbers less than a non-negative number n.

Example:

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

Solution 1: brute force

Idea:

• Loop over every number from 2 to n-1 and check if it is prime.

• To check if a number i is prime, check if it is divisible by a number from 2 to the square root of i. If yes, it is not prime.

• Why use the square root of i? Because if i has a divisor other than 1 and itself, it must also have a divisor that is no greater than its square root.

Time complexity: $O(n*\sqrt{n})$

Space complexity: $O(1)$

def countPrimes(n):
    """
    :type n: int
    :rtype: int
    """
    # corner cases
    if n <= 1:
        return 0    

    result = 0
    for i in range(2, n):
        flag = 0
        for j in range(2, int((i+1) ** 0.5 + 1)):
            if i % j == 0:
                flag = 1
                break
        if flag == 0:
            result += 1
    return result

Solution 2

Reference: Sieve of Eratosthenes https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Idea:

• Exclude the multiples of primes

• Only need to loop over from item 2 to square root of n

Time complexity: $O(n \log{\log{n}}) = O(\frac{n}{2} +\frac{n}{3} + \frac{n}{5} + \cdots)$

Space complexity: $O(n)$

def countPrimes(n):
    """
    :type n: int
    :rtype: int
    """
    # corner cases
    if n < 2:
        return 0

    # flag for each item
    is_prime = [0, 0] + [1] * (n-2)

    # loop over from item 2 to the square root of n
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i] == 1:
            is_prime[i * i:n:i] = [0] * len(is_prime[i * i:n:i])
    return sum(is_prime)