Todos os desafios
Médio 0 resolvidos 0% de aceitação

N-ésimo número primo

Retorne o n-ésimo número primo, contando o 2 como o primeiro.

O que você vai aprender

  • Gerar primos em ordem
  • Escolher um tamanho de crivo grande o bastante para a resposta
  • Comparar a divisão por tentativa com o crivo

Problema

Ver original (inglês)

Em ordem, os primos são 2, 3, 5, 7, 11, 13, … Dada uma posição n, retorne o primo que ocupa essa posição. Testar os números um a um funciona para n pequeno; para as entradas maiores, um crivo sobre um intervalo grande o suficiente é muito mais rápido.

Implemente nth_prime(n).

Entrada

n: a posição na lista de primos, começando em 1.

Saída

Retorne o n-ésimo primo. nth_prime(1) é 2.

Restrições

1 ≤ n ≤ 100 000

Exemplos

Exemplo 1
Entrada:
n = 6

Saída esperada:
expected = 13
Entrada:
long long n = 6;

Saída esperada:
long long expected = 13;
Entrada:
long n = 6;

Saída esperada:
long expected = 13;

Explicação

Os primos começam com 2, 3, 5, 7, 11, 13, então o sexto é 13.

Exemplo 2
Entrada:
n = 1

Saída esperada:
expected = 2
Entrada:
long long n = 1;

Saída esperada:
long long expected = 2;
Entrada:
long n = 1;

Saída esperada:
long expected = 2;

Explicação

O primeiro primo é 2.

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Contar os primos à medida que você os encontra funciona, mas testar cada número por divisão por tentativa fica lento para n grande.

Dica 2

O 100 000º primo é menor que 1 300 000, então um crivo desse tamanho basta.

Dica 3

Se o crivo ficar pequeno demais, dobre o tamanho e tente de novo.

Complexidade esperada

tempo O(m log log m), espaço extra O(m), em que m é o tamanho do crivo

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.