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

सबसे बड़ा अभाज्य गुणनखंड

एक धनात्मक पूर्णांक को विभाजित करने वाले सबसे बड़े अभाज्य संख्या को खोजें।

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

  • गुणनखंडों को छोटे से बड़े क्रम में भाग देकर निकालना
  • बचे हिस्से के वर्गमूल पर रुकना
  • बड़ी संख्याओं को कुशलता से संभालना

समस्या

अभाज्य संख्या वह पूर्णांक है जो 1 और स्वयं के अलावा किसी अन्य धनात्मक भाजक से विभाजित नहीं होती। n का सबसे बड़ा अभाज्य गुणनखंड खोजें। यदि n स्वयं अभाज्य है, तो n लौटाएँ।

largest_prime_factor(n) को लागू करें।

इनपुट

n: वह पूर्णांक जिसे गुणनखंडित करना है।

आउटपुट

n का सबसे बड़ा अभाज्य गुणनखंड लौटाएँ।

सीमाएँ

2 ≤ n ≤ 10¹²। इनपुट 1 को शामिल नहीं किया गया है क्योंकि इसका कोई अभाज्य गुणनखंड नहीं होता।

उदाहरण

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

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

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

अपेक्षित आउटपुट:
long expected = 7;

व्याख्या

84 = 2 × 2 × 3 × 7, इसलिए सबसे बड़ा अभाज्य गुणनखंड 7 है।

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

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

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

अपेक्षित आउटपुट:
long expected = 13;

व्याख्या

13 अभाज्य है, इसलिए वही इसका सबसे बड़ा अभाज्य गुणनखंड है।

कैसे हल करें

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

संकेत 1

छोटे prime factors पहले निकालो; बची हुई value सिर्फ घटेगी, और आख़िरी बचा factor ही answer है।

संकेत 2

Divisors को current remainder के square root तक ही test करो, और fit होने पर उसे बार-बार divide करो।

संकेत 3

अगर छोटे factors check करने के बाद remainder 1 से बड़ा है, तो वही prime है और सबसे बड़ा factor है।

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

समय O(√n), अतिरिक्त स्थान O(1)

संदर्भ

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

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

# कोडर भाषा समय मेमोरी AI रिव्यू समाधान
1 ННикита Python 949 ms - 4/5 कोड देखें
2 KKKaneki Ken Python 1,000 ms - 3/5 कोड देखें

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

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

स्पॉइलर अलर्ट: नीचे 2 पूरे समाधान पहले खुद हल करने की कोशिश करें। आप फिर भी अन्य डेवलपर्स का कोड और AI समीक्षा देख सकते हैं। चर्चा में शामिल होने के लिए साइन इन करें और चुनौती हल करें।