Count Primes
Lección 3 de 3 del curso Desafíos de programación para entrevistas - Pack V de Coddy.
Desafío
DifícilEscribe una función countPrimes que reciba un entero n, y devuelva el número de números primos que son menores que n.
Nota: La complejidad temporal debe ser mejor que O(nlogn)
1 <= n <= 1000000
Ejemplos:
Entrada - 10
Salida esperada - 4
Explicación - Hay 4 números primos menores que 10: 2, 3, 5, 7
Entrada - 13
Salida esperada - 5
Explicación - Hay 5 números primos menores que 13: 2, 3, 5, 7, 11 - ¡ten en cuenta que 13 no cuenta!
Pruébalo tú mismo
int countPrimes(int n) {
// Escribe el código aquí
}