Tous les défis
Moyen 0 résolus 0 % de réussite

Le n-ième nombre premier

Renvoyer le n-ième nombre premier, 2 étant le premier.

Ce que vous allez apprendre

  • Générer les nombres premiers dans l'ordre
  • Choisir une taille de crible suffisante pour la réponse
  • Comparer les divisions successives et le crible

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

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

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

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.