सभी चुनौतियाँ
मध्यम 0 हल किए गए 0% स्वीकृति

n-वीं अभाज्य संख्या

n-वीं अभाज्य संख्या लौटाइए, जिसमें 2 को पहली अभाज्य संख्या गिना जाता है।

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

  • अभाज्य संख्याएँ क्रम से बनाना
  • उत्तर के लिए पर्याप्त बड़ा sieve आकार चुनना
  • Trial division और sieve की तुलना करना

समस्या

क्रम से अभाज्य संख्याएँ (primes) हैं 2, 3, 5, 7, 11, 13, … आपको एक स्थान n दिया गया है, उस स्थान पर आने वाली अभाज्य संख्या लौटाइए। छोटे n के लिए संख्याओं को एक-एक करके जाँचना चल जाता है, पर बड़े इनपुट के लिए पर्याप्त बड़ी रेंज पर sieve (छलनी) कहीं ज़्यादा तेज़ है।

nth_prime(n) लिखिए।

इनपुट

n: अभाज्य संख्याओं की सूची में स्थान, जो 1 से शुरू होता है।

आउटपुट

n-वीं अभाज्य संख्या लौटाइए। nth_prime(1) का मान 2 है।

सीमाएँ

1 ≤ n ≤ 100,000

उदाहरण

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

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

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

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

व्याख्या

अभाज्य संख्याएँ 2, 3, 5, 7, 11, 13 से शुरू होती हैं, इसलिए छठी संख्या 13 है।

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

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

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

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

व्याख्या

पहली अभाज्य संख्या 2 है।

कैसे हल करें

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

संकेत 1

अभाज्य संख्याएँ मिलते-मिलते गिनना चलता है, पर हर संख्या को trial division से जाँचना बड़े n के लिए धीमा पड़ जाता है।

संकेत 2

100,000-वीं अभाज्य संख्या 1,300,000 से छोटी है, इसलिए इतने आकार का sieve काफ़ी है।

संकेत 3

अगर आपका sieve छोटा पड़ जाए, तो उसका आकार दोगुना करके फिर से कोशिश कीजिए।

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

समय O(m log log m), अतिरिक्त स्थान O(m), जहाँ m sieve का आकार है

संदर्भ

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

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

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

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

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

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