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

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.")

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__':