204. Count Primes

Task

Given an integer n, return the number of prime numbers that are strictly less than n.

Объяснение

Дано целое число n, нужно найти количество простых чисел, которые меньше n.

Простое число - это натуральное число, которое больше 1 и имеет только два натуральных делителя: 1 и само это число. Поэтому, например, числа 2, 3, 5, 7, 11 и т.д. являются простыми, а числа 4, 6, 8, 9 и т.д. - нет.

Чтобы решить эту задачу, можно использовать различные алгоритмы, но один из самых эффективных - это решето Эратосфена. Этот алгоритм основан на идее, что все составные числа могут быть представлены в виде произведения двух простых чисел. Поэтому мы можем пройти по всем числам от 2 до n и отметить каждое составное число, которое мы находим. В конце мы просто подсчитаем количество не отмеченных чисел, которые остались, и они будут простыми числами.

Example 1:

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

Example 2:

Input: n = 0
Output: 0

Example 3:

Input: n = 1
Output: 0

Constraints:

• 0 <= n <= 5 * 10^6