Formatted question description: https://leetcode.ca/all/204.html
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. @tag-hashtable
Traverse from 2 to the root number n, find the first prime number 2, and then mark all its multiples, then to the next prime number 3, mark all its multiples, and so on, until the root number n, then the unmarked numbers in are prime numbers.
We need a bool array of length n-1 to record whether each number is marked. The reason for the length of n-1 is that the title says it is the number of prime numbers less than n, not including n.