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

द्विघात व्यंजक से अभाज्य संख्याएँ

वह द्विघात व्यंजक n² + an + b खोजिए जो n = 0 से शुरू करके लगातार सबसे ज़्यादा अभाज्य संख्याएँ देता है।

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

  • Trial division से अभाज्यता जाँचना
  • दो parameters वाले space में खोज करना
  • बराबरी तोड़ने के नियम लागू करना

समस्या

कुछ द्विघात व्यंजक अभाज्य संख्याएँ बनाने में माहिर होते हैं। 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

उदाहरण

उदाहरण 1
इनपुट:
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] है।

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

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

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

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

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

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