Todos os desafios
Fácil 0 resolvidos 0% de aceitação

Contar primos em um intervalo

Conte quantos números primos existem entre dois limites, ambos incluídos.

O que você vai aprender

  • Marcar números compostos com um crivo
  • Contar os valores marcados dentro de um intervalo
  • Tratar intervalos vazios e os números 0 e 1

Problema

Ver original (inglês)

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

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

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

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.