2104 - Factorial 3

Cerința

Factorialul unui număr natural nenul n, notat n!, se defineşte ca fiind produsul numerelor naturale de la 1 la n. Una dintre modalităţile de reprezentare a factorialului este prin enumerarea factorilor primi pe care îi conţine şi a exponenţilor acestora.

Fiind dat un număr natural n, scrieţi un program care determină suma exponenţilor factorilor primi corespunzători descompunerii în factori primi a lui n factorial.

Date de intrare

Fişierul de intrare factorial3.in conţine pe prima linie numărul natural n.

Date de ieșire

Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse."

Pe următorul rând se va afișa un număr reprezentând suma exponenţilor numerelor prime din descompunerea în factori primi a lui n!.

În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse."

Restricții și precizări

• 2 ≤ n ≤ 100.000

Exemplu 1

Intrare

5

Ieșire

Datele de intrare corespund restricțiilor impuse.

5

Explicație

5! = 1*2*3*4*5 = 23*31*513+1+1=5

Exemplu 2

Intrare

1

Ieșire

Datele de intrare nu corespund restricțiilor impuse.

Rezolvare

#2104 Factorial3
def conditii(n):
    return 2 <= n <= 100_000


def factori_primi(n):
    factori = []

    # Dacă n este par, îl împărțim la 2 până nu mai este par și adăugăm 2 la lista de factori primi
    while n % 2 == 0:
        n //= 2
        factori.append(2)

    # Check odd numbers as potential factors starting from 3 up to sqrt(n)
    # Verificăm numere impare începând cu 3 până la rădăcina pătrată a lui n
    i = 3
    while i*i <= n:
        # Dacă i este factor prim, îl adăugăm la lista de factori primi
        if n % i == 0:
            n //= i
            factori.append(i)
        # Dacă nu, trecem la următorul număr impar (3+2=5, 5+2=7, 7+2=9, 9+2=11 ...)
        else:
            i += 2

    if n > 2:
        factori.append(n)

    return factori


def factorial3(n):
    factori = []
    # Pentru fiecare număr de la 2 la n+1, adăugăm factorii primi ai săi la lista de factori
    # extend() este o funcție built-in care adaugă elementele unui iterable la un alt iterable
    for i in range(2, n+1):
        factori.extend(factori_primi(i))
    # Creăm un dicționar care are ca chei factorii primi și ca valori numărul de apariții ale fiecărui factor prim
    factor_prim_nr = {}
    # Pentru fiecare factor prim din lista de factori...
    for factor in factori:
        # ...îl adăugăm în dicționar și incrementăm numărul de apariții
        # get() este o funcție built-in care returnează valoarea asociată unei chei dintr-un dicționar,
        # iar dacă cheia nu există, returnează valoarea default (în cazul nostru 0)
        factor_prim_nr[factor] = factor_prim_nr.get(factor, 0) + 1

    print(sum(factor_prim_nr.values()))


if __name__ == "__main__":
    n = int(input())
    if not conditii(n):
        print("Datele de intrare nu corespund restricțiilor impuse.")
    else:
        print("Datele de intrare corespund restricțiilor impuse.")
        factorial3(n)