Todos los desafíos
Intermedio 0 resueltos 0% de aceptación

El n-ésimo número primo

Devuelve el n-ésimo número primo, contando el 2 como el primero.

Lo que aprenderás

  • Generar primos en orden
  • Elegir un tamaño de criba suficiente para la respuesta
  • Comparar la división por tentativa con una criba

Problema

Ver original (inglés)

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

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

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

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.