Count Primes
Leçon 3 sur 3 du cours Défis de code pour l'entretien - Pack V de Coddy.
Défi
DifficileÉcrivez une fonction countPrimes qui reçoit un entier n, et retourne le nombre de nombres premiers qui sont inférieurs à n.
Note : La complexité temporelle doit être meilleure que O(nlogn)
1 <= n <= 1000000
Exemples :
Entrée - 10
Sortie attendue - 4
Explication - Il y a 4 nombres premiers inférieurs à 10 : 2, 3, 5, 7
Entrée - 13
Sortie attendue - 5
Explication - Il y a 5 nombres premiers inférieurs à 13 : 2, 3, 5, 7, 11 - notez que 13 ne compte pas !
Essayez vous-même
int countPrimes(int n) {
// Écrire le code ici
}