Problema
Los números primos, en orden, son 2, 3, 5, 7, 11, 13, … Dada una posición n, devuelve el primo que ocupa esa posición. Probar los números uno por uno funciona para valores pequeños de n, pero para las entradas grandes es mucho más rápido usar una criba sobre un intervalo lo bastante amplio.
Implementa nth_prime(n).
Entrada
n: la posición en la lista de primos, empezando en 1.
Salida
Devuelve el n-ésimo primo. nth_prime(1) es 2.
Restricciones
1 ≤ n ≤ 100,000
Ejemplos
Entrada:
n = 6
Salida esperada:
expected = 13
Entrada:
long long n = 6;
Salida esperada:
long long expected = 13;
Entrada:
long n = 6;
Salida esperada:
long expected = 13;
Explicación
Los primos empiezan 2, 3, 5, 7, 11, 13, así que el sexto es 13.
Entrada:
n = 1
Salida esperada:
expected = 2
Entrada:
long long n = 1;
Salida esperada:
long long expected = 2;
Entrada:
long n = 1;
Salida esperada:
long expected = 2;
Explicación
El primer primo es 2.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Puedes ir contando los primos a medida que los encuentras, pero probar cada número por división por tentativa se vuelve lento para n grande.
Pista 2
El primo número 100,000 es menor que 1,300,000, así que basta con una criba de ese tamaño.
Pista 3
Si la criba se queda corta, duplica su tamaño y vuelve a intentarlo.
Complejidad esperada
tiempo O(m log log m), espacio extra O(m), donde m es el tamaño de la criba
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.