Prime factorization (प्राइम फैक्टराइज़ेशन)

कोई भी धनात्मक पूर्णांक n ≥ 2 को प्राइम संख्याओं के गुणनखंड के रूप में लिखा जा सकता है:

संख्याओं के प्राइम फैक्टर खोजने के कई practically उपयोग हैं। उदाहरण के तौर पर, किसी संख्या के डिवाइज़र्स की गिनती करना बहुत आसान हो जाता है, दो संख्याओं के महत्तम समापवर्तक (GCD) और लघुत्तम समापवर्त्य (LCM) के बारे में अंदाज़ा लगाना आसान होता है, इत्यादि।

मान लीजिए हमें किसी संख्या n (उदाहरण के लिए 300) को उसके प्राइम गुणनखंडों के रूप में दर्शाना है। हम सबसे छोटे प्राइम संख्या p (2) से शुरू करते हैं और अगर n उस p से विभाजित हो सकता है, तो तब तक n को p से भाग देते रहते हैं जब तक ऐसा संभव हो (जैसे 300 / 2 = 150, 150 / 2 = 75)।

इसके बाद p को 1 से बढ़ाकर (p = 3) दोबारा जाँच करते हैं। अगर n नवीन p से विभाजित होता है, तो उसी तरह से उसे लगातार विभाजित करते रहते हैं (75 / 3 = 25)।

अब p को फिर 1 से बढ़ाकर (p = 4) देखते हैं। हालाँकि 300 एक समय पर 4 से भी विभाजित हो सकता था, पर हमने 2 से विभाजन कई बार किया है, इसलिए आगे (75 पूरा होने के बाद) 4, 6, 8, इत्यादि जैसे गैर-प्राइम या किसी पहले से इस्तेमाल हुए प्राइम के गुणांक-S (multiples) से विभाजित करना संभव नहीं रह जाता। यह क्रम सबसे छोटे से सबसे बड़े नंबर तक जाने से सुनिश्चित करता है कि आगे सिर्फ़ प्राइम संख्याएँ ही बचती हैं, जिनसे हम शेष संख्या को विभाजित कर सकते हैं।

अगले चरण में, हम p को 1 और बढ़ाकर (p = 5) जाँचते हैं (75 / 5 = 5, 5 / 5 = 1)। यह प्रक्रिया तब तक चलती रहती है जब तक जाँचने वाला भाजक से बड़ा न हो जाए। अगर इस बिंदु पर n अब भी 1 से बड़ा रह जाता है, तो यह स्वयं एक प्राइम होता है और उसे हमारे अंतिम जवाब में शामिल कर लेते हैं।

इस तरह हमारे उदाहरण में 300 को इस तरह लिखा जा सकता है: ।

n = ...                              # n को इसके प्राइम गुणनखंडों के रूप में व्यक्त करना
p, divisors, powers = 1, [], []      # p = प्राइम फैक्टर, divisors = सभी गुणनखंड, powers = उनके एक्सपोनेंट

while p * p <= n:                    # जब तक p <= sqrt(n)
    p += 1                           # हर दौर में p को 1 से बढ़ाएँ
    if n % p != 0:                   # अगर n, p से विभाजित नहीं होता तो कुछ न करें
        continue
    
    divisors.append(p)               # n % p == 0 => p एक प्राइम फैक्टर है, इसे जोड़ें
    powers.append(0)                 # एक्सपोनेंट शुरुआत में 0 रखें
    while n % p == 0:                # जितनी बार संभव हो, विभाजित करते रहें
        n //= p
        powers[-1] += 1              # हर बार भाग देने पर एक्सपोनेंट 1 बढ़ाएँ

if n > 1:                            # अगर p > sqrt(n) => n स्वयं एक प्राइम फैक्टर है
    divisors.append(n)               # n को गुणनखंड के रूप में जोड़ें
    powers.append(1)                 # इसका एक्सपोनेंट 1 होगा

print(list(zip(divisors, powers)))   # सभी गुणनखंड और उनके एक्सपोनेंट साथ में प्रिंट करें

हर iteration में, यदि संभव हो तो संख्या को उसके प्राइम फैक्टर से भाग देते हैं और साथ ही साथ एक्सपोनेंट को भी बढ़ाते जाते हैं।

आइए इस एल्गोरिद्म को कुछ संख्याओं पर चलाकर देखते हैं:

चुनौती

आपको एक पूर्णांक n दिया गया है। आपका काम है उसका सबसे बड़ा प्राइम फैक्टर पता लगाना।

इनपुट

इनपुट की पहली पंक्ति में एक अकेला पूर्णांक n (2 ≤ n ≤ ) दिया होता है।

आउटपुट

कार्यक्रम को n के सबसे बड़े प्राइम फैक्टर को प्रिंट करना चाहिए।

उदाहरण