समस्या
क्रम से अभाज्य संख्याएँ (primes) हैं 2, 3, 5, 7, 11, 13, … आपको एक स्थान n दिया गया है, उस स्थान पर आने वाली अभाज्य संख्या लौटाइए। छोटे n के लिए संख्याओं को एक-एक करके जाँचना चल जाता है, पर बड़े इनपुट के लिए पर्याप्त बड़ी रेंज पर sieve (छलनी) कहीं ज़्यादा तेज़ है।
nth_prime(n) लिखिए।
इनपुट
n: अभाज्य संख्याओं की सूची में स्थान, जो 1 से शुरू होता है।
आउटपुट
n-वीं अभाज्य संख्या लौटाइए। nth_prime(1) का मान 2 है।
सीमाएँ
1 ≤ n ≤ 100,000
उदाहरण
इनपुट:
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 है।
इनपुट:
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 के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।