Count Primes
Lição 3 de 3 do curso Desafios de Programação para Entrevistas - Pacote V da Coddy.
Desafio
DifícilEscreva uma função countPrimes que recebe um número inteiro n, e retorna o número de números primos que são menores que n.
Nota: A complexidade de tempo deve ser melhor que O(nlogn)
1 <= n <= 1000000
Exemplos:
Entrada - 10
Saída Esperada - 4
Explicação - Existem 4 números primos menores que 10: 2, 3, 5, 7
Entrada - 13
Saída Esperada - 5
Explicação - Existem 5 números primos menores que 13: 2, 3, 5, 7, 11 - note que 13 não conta!
Experimente você mesmo
int countPrimes(int n) {
// Escreva o código aqui
}