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> def validare_date(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

if __name__ == '__main__':

   n = input("Introduceti numarul n: ")
   n = validare_date(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
   else:
       print("Datele de intrare nu corespund restricțiilor impuse.")

</syntaxhighlight>

Explicație rezolvare

Acest cod primește un număr întreg pozitiv n de la utilizator și verifică dacă este un număr natural valid (adică un număr întreg pozitiv mai mare decât 1 și mai mic decât 2.100.000.000).

Dacă numărul este valid, programul afișează factorii primi ai numărului. Factorii primi sunt numerele prime care pot fi înmulțite pentru a obține numărul inițial. De exemplu, factorii primi ai numărului 12 sunt 2 și 3, deoarece 12 = 2 * 2 * 3.

Pentru a afla factorii primi ai numărului, programul împarte succesiv numărul la numerele prime începând cu 2, până când rămâne doar 1. Dacă numărul este divizibil cu un anumit număr prim, programul afișează numărul prim și de câte ori apare acesta în descompunerea factorială a numărului.

Dacă numărul nu este valid, programul afișează un mesaj corespunzător.