Editing 2104 - Factorial 3

==Cerința==
Factorialul unui număr natural nenul <code>n</code>, notat <code>n!</code>, se defineşte ca fiind produsul numerelor naturale de la <code>1</code> la <code>n</code>. 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 <code>n</code>, scrieţi un program care determină suma exponenţilor factorilor primi corespunzători descompunerii în factori primi a lui <code>n</code> factorial.

==Date de intrare==
Fişierul de intrare <code>factorial3.in</code> conţine pe prima linie numărul natural <code>n</code>.
==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 <code>n!</code>.

Î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==

*<code>2 ≤ n ≤ 100.000</code>

==Exemplu 1==
;Intrare
:5
;Ieșire
:Datele de intrare corespund restricțiilor impuse.
:5

===Explicație===
<code>5! = 1*2*3*4*5 = 23*31*51</code><code>3+1+1=5</code>

==Exemplu 2==
;Intrare
:1
;Ieșire
:Datele de intrare nu corespund restricțiilor impuse.

==Rezolvare==
<syntaxhighlight lang="python" line="1">
#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)

</syntaxhighlight>