Moyen 0 résolus 0 % de réussite

Nth Prime

Return the nth prime number, counting 2 as the first.

Ce que vous allez apprendre

  • Generate primes in order
  • Choose a sieve size large enough for the answer
  • Compare trial division with a sieve

Problème

Afficher la traduction

The primes in order are 2, 3, 5, 7, 11, 13, … Given a position n, return the prime at that position. Testing numbers one by one works for small n; for the larger inputs a sieve over a range that is big enough is much faster.

Implement nth_prime(n).

Input

n: The position in the list of primes, starting at 1.

Output

Return the nth prime. nth_prime(1) is 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

The primes start 2, 3, 5, 7, 11, 13, so the sixth one is 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

The first prime is 2.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Counting primes as you find them works, but testing every number by trial division gets slow for large n.

Indice 2

The 100,000th prime is below 1,300,000, so a sieve of that size is enough.

Indice 3

If your sieve turns out too small, double it and try again.

Complexité attendue

O(m log log m) time, O(m) extra space, where m is the sieve size

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.