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