Tous les défis
Facile 0 résolus 0 % de réussite

Compter les nombres premiers dans un intervalle

Compter les nombres premiers compris entre deux bornes incluses.

Ce que vous allez apprendre

  • Marquer les nombres composés avec un crible
  • Compter les valeurs marquées dans un intervalle
  • Gérer les intervalles vides et les nombres 0 et 1

Problème

Combien y a-t-il de nombres premiers entre 1 et 100 ? Entre 50 et 60 ? Comptez les nombres premiers p tels que low ≤ p ≤ high. N'oubliez pas que 0 et 1 ne sont pas premiers. Un crible jusqu'à high donne la réponse rapidement.

Implémentez count_primes_in_range(low, high).

Entrée

low : la borne inférieure, incluse.

high : la borne supérieure, incluse.

Sortie

Renvoyez le nombre de nombres premiers dans l'intervalle. Si low > high, l'intervalle est vide et la réponse est 0.

Contraintes

0 ≤ low ≤ 1 000 000

0 ≤ high ≤ 1 000 000

Exemples

Exemple 1
Entrée :
low = 1
high = 100

Sortie attendue :
expected = 25
Entrée :
long long low = 1;
long long high = 100;

Sortie attendue :
long long expected = 25;
Entrée :
long low = 1;
long high = 100;

Sortie attendue :
long expected = 25;

Explication

Il y a 25 nombres premiers jusqu'à 100 (2, 3, 5, … 97), donc la réponse est 25.

Exemple 2
Entrée :
low = 50
high = 60

Sortie attendue :
expected = 2
Entrée :
long long low = 50;
long long high = 60;

Sortie attendue :
long long expected = 2;
Entrée :
long low = 50;
long high = 60;

Sortie attendue :
long expected = 2;

Explication

Entre 50 et 60, seuls 53 et 59 sont premiers, donc la réponse est 2.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Construisez un crible jusqu'à high en barrant les multiples de chaque nombre premier à partir de son carré.

Indice 2

Comptez ensuite les nombres encore marqués comme premiers entre low et high.

Indice 3

Si low est supérieur à high, il n'y a rien à calculer.

Complexité attendue

temps O(high log log high), espace supplémentaire O(high)

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.