समस्या
जुड़वाँ अभाज्य संख्याएँ (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
उदाहरण
इनपुट:
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]] मिलता है।
इनपुट:
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 के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।