मध्यम 0 हल किए गए 0% स्वीकृति

Nth Prime

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

आप क्या सीखेंगे

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

समस्या

अनुवाद दिखाएँ

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.

सीमाएँ

1 ≤ n ≤ 100,000

उदाहरण

उदाहरण 1
इनपुट:
n = 6

अपेक्षित आउटपुट:
expected = 13
इनपुट:
long long n = 6;

अपेक्षित आउटपुट:
long long expected = 13;
इनपुट:
long n = 6;

अपेक्षित आउटपुट:
long expected = 13;

व्याख्या

The primes start 2, 3, 5, 7, 11, 13, so the sixth one is 13.

उदाहरण 2
इनपुट:
n = 1

अपेक्षित आउटपुट:
expected = 2
इनपुट:
long long n = 1;

अपेक्षित आउटपुट:
long long expected = 2;
इनपुट:
long n = 1;

अपेक्षित आउटपुट:
long expected = 2;

व्याख्या

The first prime is 2.

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

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

संकेत 2

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

संकेत 3

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

अपेक्षित जटिलता

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

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।