Reference: LeetCode
Difficulty: Easy

## Problem

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

Example:

## Analysis

Methods:

1. Brute-Force

Time: $O(N^2)$
Space: $O(1)$

1. Using Square Root
• If n is not prime, n = a x b, a <= b => a <= sqrt(n).
• Note:
• Use i * i <= num rather than i <= Math.sqrt(num), since the former one is faster.
• Use i * i <= num instead of i * i < num, the latter one is incorrect.

Time: $O(N\sqrt{N}) = O(N^{1.5})$
Space: $O(1)$

1. Sieve of Eratosthenes
• The basic idea is to remove primes’ multiples till $n - 1$.
• Some Optimizations:
• We don’t need to process potential primes larger than $\sqrt{n}$, since those non-prime numbers which are larger than $\sqrt{n}$ have already been struck off by the multiples of the primes less than or equal to $\sqrt{n}$.
• Each multiple j of a prime i can start from i * i since the smaller multiples have been struck off by other smaller primes.

Time: $\frac{N}{2} + \frac{N}{3} + \frac{N}{5} + \ldots = O(N\log{\log{N}}) \sim O(N)$
Space: $O(N)$ Comment Junhao Wang
Hi, I was a master student at USC studying Computer Science.