Problème
Un nombre premier est un entier strictement supérieur à 1 qui n'est divisible que par 1 et lui-même. Additionnez tous les nombres premiers strictement inférieurs à la limite. La limite elle-même est exclue, même si elle est première.
Implémentez prime_sum(limit).
Entrée
limit : La borne supérieure exclusive.
Sortie
Retournez la somme des nombres premiers admissibles, ou 0 s'il n'y en a aucun.
Contraintes
0 ≤ limit ≤ 2 000 000. Retournez la somme en utilisant un entier signé 64 bits.
Exemples
Entrée :
limit = 12
Sortie attendue :
expected = 28Entrée :
long long limit = 12;
Sortie attendue :
long long expected = 28;Entrée :
long limit = 12;
Sortie attendue :
long expected = 28;Explication
Les nombres premiers inférieurs à 12 sont 2, 3, 5, 7 et 11 ; leur somme est 28.
Entrée :
limit = 2
Sortie attendue :
expected = 0Entrée :
long long limit = 2;
Sortie attendue :
long long expected = 0;Entrée :
long limit = 2;
Sortie attendue :
long expected = 0;Explication
Il n'y a aucun nombre premier strictement inférieur à 2.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Le coût principal est de trouver les nombres premiers efficacement ; des tests de divisibilité naïfs pour chaque nombre seront trop lents.
Indice 2
Utilise une méthode de type crible pour marquer les composés, puis additionne les nombres non marqués et strictement inférieurs à la limite.
Indice 3
Souviens-toi que la limite elle-même est exclue, même si elle est première, et que les petites limites peuvent ne rien ajouter.
Complexité attendue
temps O(limit log log limit), espace supplémentaire O(limit)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.