समस्या
अभाज्य संख्या वह पूर्णांक है जो 1 और स्वयं के अलावा किसी अन्य धनात्मक भाजक से विभाजित नहीं होती। n का सबसे बड़ा अभाज्य गुणनखंड खोजें। यदि n स्वयं अभाज्य है, तो n लौटाएँ।
largest_prime_factor(n) को लागू करें।
इनपुट
n: वह पूर्णांक जिसे गुणनखंडित करना है।
आउटपुट
n का सबसे बड़ा अभाज्य गुणनखंड लौटाएँ।
सीमाएँ
2 ≤ n ≤ 10¹²। इनपुट 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 है।
इनपुट:
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 के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।