# Question

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


# Algorithm

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.

Java