एल्गोरिथ्म्स और डेटा स्ट्रक्चर्स

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 = 24
  1. p = 2, n = 24 (हमने लूप की शुरुआत में p को 1 से बढ़ाकर 2 बनाया) n % 2 == 0 ⇒ divisors = [2], powers = [0] n //= 2 ⇒ n = 12, powers = [1] n //= 2 ⇒ n = 6, powers = [2] n //= 2 ⇒ n = 3, powers = [3]
  1. p = 3, n = 3 ⇒ अब p * p = 9 (जो 3 से बड़ा है), इसलिए while लूप रुकेगा
  1. n > 1 ⇒ divisors = [2, 3], powers = [3, 1]
n = 75
  1. p = 2, n = 75
  1. p = 3, n = 75 n % 3 == 0 ⇒ divisors = [3], powers = [0] n //= 3 ⇒ n = 25, powers = [1]
  1. p = 4, n = 25
  1. p = 5, n = 25 n % 5 == 0 ⇒ divisors = [3, 5], powers = [1, 0] n //= 5 ⇒ n = 5, powers = [1, 1] n //= 5 ⇒ n = 1, powers = [1, 2]
  1. p * p > n ⇒ while लूप समाप्त ⇒ divisors = [3, 5], powers = [1, 2]
n = 84
  1. p = 2, n = 84 n % 2 == 0 ⇒ divisors = [2], powers = [0] n //= 2 ⇒ n = 42, powers = [1] n //= 2 ⇒ n = 21, powers = [2]
  1. p = 3, n = 21 n % 3 == 0 ⇒ divisors = [2, 3], powers = [2, 0] n //= 3 ⇒ n = 7, powers = [2, 1]
  1. p * p > n ⇒ while लूप समाप्त
  1. n > 1 ⇒ divisors = [2, 3, 7], powers = [2, 1, 1]
n = 31
  1. p = 2, n = 31
  1. p = 3, n = 31
  1. p = 4, n = 31
  1. p = 5, n = 31
  1. p = 6, n = 31
  1. p * p > n ⇒ while लूप समाप्त
  1. n > 1 ⇒ divisors = [31], powers = [1]

चुनौती

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

इनपुट

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

आउटपुट

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

उदाहरण

इनपुट
आउटपुट
8
2
24
3
75
5
31
31
बोनस: हम केवल प्राइम संख्याओं के लिए ही जाँच क्यों नहीं करते?
वर्तमान एल्गोरिद्म में हम 2, 3, 4, … से लेकर तक सभी संख्याओं की जाँच करते हैं। पहली नज़र में यह लगता है कि शायद केवल प्राइम संख्याओं का उपयोग करना बेहतर हो सकता है। लेकिन तक के सभी प्राइम संख्याओं को निकालने में लगभग समय लगेगा, जो कि सीधे 2 से लेकर तक जाँचने की तुलना में ज़्यादा हो सकता है।
हालाँकि, कुछ परिस्थितियों में पहले से ही प्राइम संख्याओं की सूची तैयार रखना उपयोगी हो सकता है, जिससे बाद में केवल उन्हीं का उपयोग करके प्राइम फैक्टर निकालना ज़्यादा व्यवहारिक हो जाता है। इस पर आप क्या सोचते हैं?
 
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue