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==
Fişierul de ieşire <code>factorial3.out</code> va conţine pe prima linie un număr reprezentând suma exponenţilor numerelor prime din descompunerea în factori primi a lui <code>n!</code>.

==Restricții și precizări==

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

==Exemplu 1==
;Intrare
:5
;Ieșire
:5

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

<code>3+1+1=5</code>

==Exemplu 2==
;Intrare
:1
;Ieșire
:1

==Rezolvare==
<syntaxhighlight lang="python" line="1">
#2104 Factorial3
import math


def factori_primi(n):
    factori = []

    while n % 2 == 0:
        n = int(n / 2)
        factori.append(2)

    for i in range(3, int(math.sqrt(n))+1, 2):
        while n % i == 0:
            factori.append(i)
            n = int(n / i)
    if n > 2:
        factori.append(n)

    return factori


def suma_exponenti_nr_prime(n):
    factori = []
    for i in range(2, n+1):
        factori.extend(factori_primi(i))
    factor_prim_nr = {}
    for factor in factori:
        factor_prim_nr[factor] = factor_prim_nr.get(factor, 0) + 1
    return sum(factor_prim_nr.values())


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


def main():
    n = int(input())
    if not conditii(n):
        return print("Date de intrare gresite!")

    print(suma_exponenti_nr_prime(n))


if __name__ == "__main__":
    main()

</syntaxhighlight>