0062 - Factorizare

Cerinţa

Se citeşte un număr natural n. Să se afişeze descompunerea în factori primi a lui n.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieşire

Programul afișează pe ecran perechile b p, reprezentând factorii primi şi puterile corespunzătoare. Perechile se afişează câte una pe o linie a ecranului, în ordinea crescătoare a bazelor. Cele două valori din pereche sunt separate printr-un spaţiu.

Restricții și precizări

• 1 < n < 2.100.000.000

Exemplu

Intrare

135

Ieșire

3 3

5 1

Explicație

• 135 = 33 * 51.

Rezolvare

<syntaxhighlight lang="python" line> import math

def validare_natural(n):

   try:
       n = int(n)
       if n > 1 and n < 2100000000:
           return n
       else:
           print("Numarul trebuie sa fie un numar natural mai mare decat 1 si mai mic decat 2100000000.")
           return None
   except ValueError:
       print("Nu ati introdus un numar natural valid.")
       return None

n = input("Introduceti numarul n: ") n = validare_natural(n)

if n:

   i = 2
   while i <= n:
       p = 0
       while n % i == 0:
           p += 1
           n //= i
       if p > 0:
           print(i, p)
       i += 1

</syntaxhighlight>