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

जुड़वाँ अभाज्य संख्याएँ

दी गई सीमा तक के सभी जुड़वाँ अभाज्य जोड़े (p, p + 2) बताइए।

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

  • छलनी से सीमा तक की अभाज्य संख्याएँ चिह्नित करना
  • 2 के अंतर वाली अभाज्य संख्याएँ खोजना
  • इतनी छोटी सीमाओं को संभालना जिनमें कोई जोड़ा नहीं आता

समस्या

जुड़वाँ अभाज्य संख्याएँ (twin primes) ऐसी दो अभाज्य संख्याएँ हैं जिनका अंतर 2 हो, जैसे 11 और 13 या 17 और 19। ऐसे सभी जोड़े ढूँढिए जिनकी बड़ी संख्या limit से अधिक न हो।

twin_primes(limit) लिखिए।

बड़ी सीमाओं के लिए हर संख्या को अलग-अलग जाँचने की बजाय छलनी (sieve) से सारी अभाज्य संख्याएँ एक साथ निकालिए।

इनपुट

limit: जोड़े की बड़ी अभाज्य संख्या का अधिकतम संभव मान।

आउटपुट

जोड़ों [p, p + 2] की list लौटाइए, जहाँ दोनों संख्याएँ अभाज्य हों और p + 2 ≤ limit हो, और जोड़े p के आरोही क्रम में हों। कोई जोड़ा न हो तो खाली list लौटाइए।

सीमाएँ

0 ≤ limit ≤ 10^6

उदाहरण

उदाहरण 1
इनपुट:
limit = 20

अपेक्षित आउटपुट:
expected = [
    [3, 5],
    [5, 7],
    [11, 13],
    [17, 19]
]
इनपुट:
long long limit = 20;

अपेक्षित आउटपुट:
std::vector<std::vector<long long>> expected = {
    {3, 5},
    {5, 7},
    {11, 13},
    {17, 19}
};
इनपुट:
long limit = 20;

अपेक्षित आउटपुट:
long[][] expected = new long[][] {
    new long[] {3, 5},
    new long[] {5, 7},
    new long[] {11, 13},
    new long[] {17, 19}
};

व्याख्या

20 तक की अभाज्य संख्याएँ 2, 3, 5, 7, 11, 13, 17, 19 हैं; इनमें 2 के अंतर वाली संख्याओं से [[3, 5], [5, 7], [11, 13], [17, 19]] मिलता है।

उदाहरण 2
इनपुट:
limit = 6

अपेक्षित आउटपुट:
expected = [
    [3, 5]
]
इनपुट:
long long limit = 6;

अपेक्षित आउटपुट:
std::vector<std::vector<long long>> expected = {
    {3, 5}
};
इनपुट:
long limit = 6;

अपेक्षित आउटपुट:
long[][] expected = new long[][] {
    new long[] {3, 5}
};

व्याख्या

3 और 5 दोनों अभाज्य हैं और 5 ≤ 6, लेकिन 7 सीमा से बाहर है, इसलिए केवल [[3, 5]]।

कैसे हल करें

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

संकेत 1

छलनी 10^6 तक की सभी अभाज्य संख्याएँ हर संख्या को अलग से जाँचने के मुक़ाबले कहीं तेज़ी से ढूँढ लेती है।

संकेत 2

फिर हर उस p को जाँचिए जिसके लिए p + 2 ≤ limit हो।

संकेत 3

पहला जोड़ा (3, 5) है, इसलिए 5 से छोटी किसी भी सीमा पर खाली list मिलती है।

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

समय O(limit log log limit), अतिरिक्त स्थान O(limit)

संदर्भ

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

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

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

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

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

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