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

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

<syntaxhighlight lang="python" line="1">

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("Datele de intrare nu corespund restricțiilor impuse.")
   print("Datele de intrare corespund restricțiilor impuse.")

   print(suma_exponenti_nr_prime(n))

if __name__ == "__main__":

   main()

</syntaxhighlight>