0063 - Factorizare 1

Cerinţa

Să se scrie un program care citeşte un număr natural n şi determină factorul care apare în descompunerea în factori primi a lui n la puterea cea mai mare.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieşire

Programul afișează pe ecran numărul prim p, cu semnificaţia precizată.

Restricții și precizări

• 1 < n < 1.000.000.000
• dacă în descompunerea în factori primi a lui n apar mai mulţi factori la puterea maximă, se va afişa cel mai mare dintre ei

Exemplu

Intrare

405

Ieșire

3

Explicație

405 = 34 * 51. Astfel, factorul care apare la puterea cea mai mare este 3.

Rezolvare

<syntaxhighlight lang="python" line>

def validare_date(n):

   if n <= 1 or n >= 1000000000:
       return False
   return True

if __name__ == '__main__':

   n = int(input("Introduceți numărul n: "))

   if validare_date(n):
    
       factors = {}
       d = 2
       while d*d <= n:
           while (n % d) == 0:
               if d in factors:
                   factors[d] += 1
               else:
                   factors[d] = 1
               n //= d
           d += 1
       if n > 1:
           if n in factors:
               factors[n] += 1
           else:
               factors[n] = 1
      
       max_factor = 0
       max_power = 0
       for factor, power in factors.items():
           if power > max_power:
               max_factor = factor
               max_power = power

       print(f"Factorul cu puterea cea mai mare în descompunerea lui n este {max_factor}")
       print("\nDatele de intrare corespund restricțiilor impuse.\n")
   else:
       print("Datele de intrare nu corespund restricțiilor impuse.")

</syntaxhighlight>

Explicație rezolvare

Problema cere să scriem un program în Python care primește un număr natural n și determină factorul care apare în descompunerea în factori primi a lui n la puterea cea mai mare. Algoritmul constă în factorizarea în factori primi a lui n și stocarea acestora într-un dicționar, apoi determinarea factorului cu puterea cea mai mare prin parcurgerea dicționarului. Pentru a valida datele de intrare, am scris o funcție validare_date care verifică dacă numărul n se află în intervalul impus de restricții. Programul afișează mesaje corespunzătoare în funcție de validitatea datelor de intrare prin utilizarea instrucțiunii if __name__ == '__main__':