Problema
Quantos primos existem de 1 a 100? E de 50 a 60? Conte os primos p com low ≤ p ≤ high. Lembre-se de que 0 e 1 não são primos. Um crivo até high responde isso rapidamente.
Implemente count_primes_in_range(low, high).
Entrada
low: o limite inferior, incluído.
high: o limite superior, incluído.
Saída
Retorne a quantidade de primos no intervalo. Se low > high, o intervalo é vazio e a resposta é 0.
Restrições
0 ≤ low ≤ 1 000 000
0 ≤ high ≤ 1 000 000
Exemplos
Entrada:
low = 1
high = 100
Saída esperada:
expected = 25
Entrada:
long long low = 1;
long long high = 100;
Saída esperada:
long long expected = 25;
Entrada:
long low = 1;
long high = 100;
Saída esperada:
long expected = 25;
Explicação
Há 25 primos até 100 (2, 3, 5, … 97), então a resposta é 25.
Entrada:
low = 50
high = 60
Saída esperada:
expected = 2
Entrada:
long long low = 50;
long long high = 60;
Saída esperada:
long long expected = 2;
Entrada:
long low = 50;
long high = 60;
Saída esperada:
long expected = 2;
Explicação
Entre 50 e 60, só 53 e 59 são primos, então a resposta é 2.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Monte um crivo até high, riscando os múltiplos de cada primo a partir do quadrado dele.
Dica 2
Depois, conte os números de low a high que continuam marcados como primos.
Dica 3
Se low for maior que high, não é preciso calcular nada.
Complexidade esperada
tempo O(high log log high), espaço extra O(high)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.