[Leetcode 204] Count Primes

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

Hint:
Let's start with a isPrime function. To determine if a number is prime, we need to check if it is not divisible by any number less than n.
The runtime complexity of isPrime function would be O(n) and hence counting the total prime numbers up to n would be O(n2). Could we do better?

Diffculty
Easy

Similar Problems
[LeetCode ] Ugly Number Easy [LeetCode ] Ugly Number II Medium [LeetCode ] Perfect Squares Medium

Analysis