1474 - Exponent

Enunț

Softescu a învăţat azi la şcoală, la ora de informatică algoritmul determinării exponentului unui număr natural prim p în descompunerea în factori primi a lui n!. Softescu s-a gândit că ar fi interesant dacă ar putea să elaboreze un algoritm care să determine exponentul unui număr natural oarecare, a (a>1) în descompunerea în factori primi a lui n!.

Cerința

Dându-se două numere naturale n şi a, nenule, se cere să se determine exponentul numărului natural a în descompunerea lui n!.

Date de intrare

Fişierul de intrare exponentin.txt conţine pe prima linie două numere naturale, nenule, n a separate printr-un spațiu.

Date de ieșire

Fişierul de ieşire exponentout.txt va conţine pe prima linie un număr natural e, reprezentând exponentul numărului natural a în descompunerea în factori primi a lui n!

Restricții și precizări

• 2 ⩽ n, a ⩽ 1000
• exponentul unui număr natural nenul x, nu neapărat prim, în descompunerea unui număr natural nenul y este cel mai mare număr natural e cu proprietatea că xe este divizor al lui y.

Exemplul 1

Intrare

exponentin.txt

6 4

Ieșire

Datele de intrare corespund restricțiilor impuse

exponentout.txt

2

Explicație

6!=1*2*3*4*5*6 = 1*3*3*4*4*5.

Exemplul 2

Intrare

exponentin.txt

1 4

Ieșire

Datele de intrare NU corespund restricțiilor impuse

Rezolvare

#1474 - Exponent

def validare_date(n, a):
    if not (2 <= n <= 1000 and 2 <= a <= 1000):
        return False
    return True


def exponent_in_descompunere(n, a):
    if validare_date(n, a):
        print("Datele de intrare corespund restricțiilor impuse")

        def calculeaza_exponent(prima_putere, numar):
            exponent = 0
            while numar % prima_putere == 0:
                exponent += 1
                numar //= prima_putere
            return exponent
        factorial_n = 1
        for i in range(2, n + 1):
            factorial_n *= i
        exponent_a = calculeaza_exponent(a, factorial_n)
        return exponent_a
    else:
        print("Datele de intrare NU corespund restricțiilor impuse")
        exit(0)


with open("exponentin.txt", "r") as file:
    n, a = map(int, file.readline().split())

with open("exponentout.txt", "w") as file:
    exponent_a = exponent_in_descompunere(n, a)
    file.write(str(exponent_a))