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