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

गोल्डबाख़ विभाजन

किसी सम संख्या को दो अभाज्य संख्याओं के योग के रूप में लिखिए, जिसमें पहली अभाज्य संख्या जितनी हो सके उतनी छोटी हो।

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

  • √n पर रुकने वाली trial division की अभाज्य जाँच लिखना
  • उम्मीदवारों को बढ़ते क्रम में खोजना और पहले सही उत्तर पर रुकना
  • जोड़े को माँगे गए क्रम में लौटाना

समस्या

गोल्डबाख़ का अनुमान (Goldbach's conjecture) कहता है कि 2 से बड़ी हर सम संख्या दो अभाज्य संख्याओं का योग होती है। इसे आज तक सिद्ध नहीं किया जा सका है, लेकिन यहाँ दी गई संख्याओं से कहीं आगे तक इसकी जाँच हो चुकी है। अक्सर कई तरीक़े होते हैं: 28 = 5 + 23 = 11 + 17। वह तरीक़ा ढूँढिए जिसमें छोटी अभाज्य संख्या जितनी हो सके उतनी छोटी हो।

goldbach_partition(n) लिखिए।

p = 2, 3, 5, ... आज़माते हुए यह जाँचिए कि n − p अभाज्य है या नहीं; उत्तर जल्दी मिल जाता है, क्योंकि छोटा p लगभग हमेशा काम कर जाता है। 10^9 तक की किसी संख्या को trial division से अभाज्य जाँचने के लिए लगभग 31,623 तक के भाजक ही आज़माने पड़ते हैं।

इनपुट

n: 2 से बड़ी एक सम संख्या।

आउटपुट

[p, q] लौटाइए, जहाँ p और q अभाज्य हों, p + q = n, p ≤ q, और p वह सबसे छोटी अभाज्य संख्या हो जिसके लिए यह संभव है।

सीमाएँ

4 ≤ n ≤ 10^9, n सम है

उदाहरण

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

अपेक्षित आउटपुट:
expected = [5, 23]
इनपुट:
long long n = 28;

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

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

व्याख्या

28 − 2 = 26 और 28 − 3 = 25 अभाज्य नहीं हैं, लेकिन 28 − 5 = 23 अभाज्य है, इसलिए उत्तर [5, 23] है।

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

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

अपेक्षित आउटपुट:
std::vector<long long> expected = {2, 2};
इनपुट:
long n = 4;

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

व्याख्या

एकमात्र विकल्प 2 + 2 है, इसलिए उत्तर [2, 2] है।

कैसे हल करें

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

संकेत 1

p = 2, 3, 4, ... आज़माइए और उस पहले p पर रुक जाइए जहाँ p और n − p दोनों अभाज्य हों।

संकेत 2

अभाज्यता जाँचने के लिए केवल वर्गमूल तक के भाजक आज़माने होते हैं।

संकेत 3

चूँकि आप सबसे छोटे p पर रुकते हैं, p ≤ n − p अपने-आप सही रहता है।

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

समय O(k √n), जहाँ k आज़माए गए उम्मीदवारों की संख्या है, अतिरिक्त स्थान O(1)

संदर्भ

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

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

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

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

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

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