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

Count Primes in a Range

Count how many prime numbers lie between two bounds, both included.

Ce que vous allez apprendre

  • Mark composite numbers with a sieve
  • Count marked values inside a range
  • Handle empty ranges and the numbers 0 and 1

Problème

Afficher la traduction

How many primes are there from 1 to 100? From 50 to 60? Count the primes p with low ≤ p ≤ high. Remember that 0 and 1 are not prime. A sieve up to high answers this quickly.

Implement count_primes_in_range(low, high).

Input

low: The lower bound, included.

high: The upper bound, included.

Output

Return the number of primes in the range. If low > high the range is empty and the answer is 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

There are 25 primes up to 100 (2, 3, 5, … 97), so the answer is 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

Only 53 and 59 are prime between 50 and 60, so the answer is 2.

Comment l'aborder

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

Indice 1

Build a sieve up to high, crossing out multiples of each prime starting at its square.

Indice 2

Then count the numbers still marked prime from low to high.

Indice 3

If low is greater than high, nothing needs to be computed.

Complexité attendue

O(high log log high) time, O(high) extra space

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.