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
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.
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.