समस्या
कुछ द्विघात व्यंजक अभाज्य संख्याएँ बनाने में माहिर होते हैं। n² + n + 41 से n = 0 से 39 तक अभाज्य संख्याएँ ही मिलती हैं। ऐसे पूर्णांकों a और b के लिए जिनमें |a| ≤ limit और |b| ≤ limit हो, गिनिए कि लगातार कितने मानों n = 0, 1, 2, ... पर n² + an + b अभाज्य है; पहले ऐसे मान पर रुक जाइए जिस पर परिणाम अभाज्य न हो। सबसे लंबी लगातार श्रृंखला (run) वाला जोड़ा खोजिए।
quadratic_primes(limit) लिखिए।
इनपुट
limit: a और b के निरपेक्ष मानों की सीमा।
आउटपुट
[a, b, run] लौटाइए, जहाँ run सबसे लंबी श्रृंखला में मिली अभाज्य संख्याओं की गिनती है। अगर कई जोड़े बराबरी पर हों तो सबसे छोटा a लीजिए, फिर सबसे छोटा b। 2 से छोटी संख्याएँ अभाज्य नहीं होतीं, इसलिए जिस जोड़े का मान n = 0 पर अभाज्य नहीं है, उसका run 0 है।
सीमाएँ
0 ≤ limit ≤ 300
उदाहरण
इनपुट:
limit = 3
अपेक्षित आउटपुट:
expected = [-2, 3, 3]
इनपुट:
long long limit = 3;
अपेक्षित आउटपुट:
std::vector<long long> expected = {-2, 3, 3};
इनपुट:
long limit = 3;
अपेक्षित आउटपुट:
long[] expected = new long[] {-2, 3, 3};
व्याख्या
a = −2 और b = 3 के साथ n = 0, 1, 2, 3 पर मान 3, 2, 3, 6 हैं, यानी तीन अभाज्य। कोई जोड़ा इससे बेहतर नहीं है और कोई छोटा a बराबरी नहीं करता, इसलिए उत्तर [-2, 3, 3] है।
इनपुट:
limit = 1
अपेक्षित आउटपुट:
expected = [-1, -1, 0]
इनपुट:
long long limit = 1;
अपेक्षित आउटपुट:
std::vector<long long> expected = {-1, -1, 0};
इनपुट:
long limit = 1;
अपेक्षित आउटपुट:
long[] expected = new long[] {-1, -1, 0};
व्याख्या
b का मान −1, 0 या 1 है और इनमें से कोई अभाज्य नहीं, इसलिए हर run 0 है और सबसे छोटा जोड़ा चुना जाता है: [-1, -1, 0]।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
n = 0 पर मान b होता है, इसलिए कोई भी run बनने के लिए b का अभाज्य होना ज़रूरी है।
संकेत 2
n को तब तक बढ़ाते जाइए जब तक मान अभाज्य न रहे; ऋणात्मक मान और 2 से छोटे मान run को ख़त्म कर देते हैं।
संकेत 3
a और b को बढ़ते क्रम में loop कीजिए, और सबसे अच्छे जोड़े को सिर्फ़ सख़्ती से लंबे run पर बदलिए।
अपेक्षित जटिलता
समय O(limit² × run × √V), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।