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

अभाज्य गुणनखंडन

किसी संख्या को उसके अभाज्य गुणनखंडों में तोड़िए, छोटे से बड़े क्रम में और दोहराव सहित।

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

  • हर गुणनखंड से उतनी बार भाग देना जितनी बार वह आता है
  • d × d के बचे हुए हिस्से से बड़ा होते ही trial division रोकना
  • समझना कि अंत में 1 से बड़ा बचा हिस्सा एक अभाज्य गुणनखंड है

समस्या

1 से बड़े हर पूर्णांक को अभाज्य संख्याओं के गुणनफल के रूप में ठीक एक ही तरह से लिखा जा सकता है, गुणनखंडों के क्रम को छोड़कर (यह अंकगणित का मूलभूत प्रमेय है)। उदाहरण के लिए, 360 = 2 × 2 × 2 × 3 × 3 × 5। यह सूची निकालने को अभाज्य गुणनखंडन (prime factorization) कहते हैं।

prime_factorization(n) लिखिए।

n 10^12 तक हो सकता है, इसलिए पारंपरिक तरीक़ा trial division है: जब तक हो सके 2 से भाग दीजिए, फिर 3 से, और इसी तरह आगे। भाजक d को तभी तक आज़माना है जब तक d × d, n के बचे हुए हिस्से से बड़ा न हो जाए; अंत में 1 से बड़ा जो कुछ बचे, वह ख़ुद अभाज्य है। इससे काम लगभग √n ≈ 10^6 कदमों तक सीमित रहता है, चाहे n कोई बड़ी अभाज्य संख्या हो या दो बड़ी अभाज्य संख्याओं का गुणनफल।

इनपुट

n: वह संख्या जिसके गुणनखंड निकालने हैं।

आउटपुट

n के अभाज्य गुणनखंड आरोही क्रम में लौटाइए, हर अभाज्य संख्या को उतनी बार दोहराते हुए जितनी बार वह n को विभाजित करती है, ताकि list का गुणनफल n हो। n = 1 के लिए खाली list लौटाइए। अगर n अभाज्य है, तो list में केवल एक तत्व n होगा।

सीमाएँ

1 ≤ n ≤ 10^12

उदाहरण

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

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

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

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

व्याख्या

360 = 2 × 180 = 2 × 2 × 90 = 2 × 2 × 2 × 45 = 2 × 2 × 2 × 3 × 15 = 2 × 2 × 2 × 3 × 3 × 5, इसलिए उत्तर [2, 2, 2, 3, 3, 5] है।

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

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

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

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

व्याख्या

√97 ≈ 9.8 तक की कोई भी अभाज्य संख्या (2, 3, 5, 7) 97 को विभाजित नहीं करती, इसलिए 97 अभाज्य है और उत्तर [97] है।

कैसे हल करें

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

संकेत 1

जब तक हो सके 2 से भाग दीजिए, फिर 3, 5, 7 और आगे बढ़िए।

संकेत 2

हर गुणनखंड मिलने पर n को छोटा कीजिए, और d × d की तुलना छोटे हुए n से कीजिए।

संकेत 3

लूप के बाद अगर 1 से बड़ा कुछ बचे, तो वही सबसे बड़ा अभाज्य गुणनखंड है।

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

समय O(√n), परिणाम के लिए अतिरिक्त स्थान O(log n)

संदर्भ

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

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

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

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

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

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