Problème
Rangés dans l'ordre, les nombres premiers sont 2, 3, 5, 7, 11, 13, … Étant donné un rang n, renvoyez le nombre premier qui occupe ce rang. Tester les nombres un par un suffit quand n est petit ; pour les grandes valeurs, un crible sur un intervalle assez grand est bien plus rapide.
Implémentez nth_prime(n).
Entrée
n : le rang dans la liste des nombres premiers, à partir de 1.
Sortie
Renvoyez le n-ième nombre premier. nth_prime(1) vaut 2.
Contraintes
1 ≤ n ≤ 100 000
Exemples
Entrée :
n = 6
Sortie attendue :
expected = 13
Entrée :
long long n = 6;
Sortie attendue :
long long expected = 13;
Entrée :
long n = 6;
Sortie attendue :
long expected = 13;
Explication
Les nombres premiers commencent par 2, 3, 5, 7, 11, 13, donc le sixième est 13.
Entrée :
n = 1
Sortie attendue :
expected = 2
Entrée :
long long n = 1;
Sortie attendue :
long long expected = 2;
Entrée :
long n = 1;
Sortie attendue :
long expected = 2;
Explication
Le premier nombre premier est 2.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Compter les nombres premiers au fur et à mesure fonctionne, mais tester chaque nombre par divisions successives devient lent pour un grand n.
Indice 2
Le 100 000e nombre premier est inférieur à 1 300 000, donc un crible de cette taille suffit.
Indice 3
Si votre crible s'avère trop petit, doublez sa taille et recommencez.
Complexité attendue
temps O(m log log m), espace supplémentaire O(m), où m est la taille du crible
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.