Count Primes
Урок 3 из 3 курса Задачи для подготовки к интервью — Пакет V на Coddy.
Задание
СложноНапишите функцию countPrimes, которая принимает целое число n и возвращает количество простых чисел, которые меньше n.
Примечание: Временная сложность должна быть лучше, чем O(nlogn)
1 <= n <= 1000000
Примеры:
Ввод - 10
Ожидаемый результат - 4
Объяснение - Существует 4 простых числа меньше 10: 2, 3, 5, 7
Ввод - 13
Ожидаемый результат - 5
Объяснение - Существует 5 простых чисел меньше 13: 2, 3, 5, 7, 11 - обратите внимание, что 13 не считается!
Попробуйте сами
int countPrimes(int n) {
// Напишите здесь код
}