1319 - Descompunere factori

Cerinţa

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

Date de intrare

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

Date de ieşire

Programul va afișa pe ecran factorii primi ai lui n în ordine crescătoare, separați prin câte un spațiu.

Restricții și precizări

• 2 ≤ n ≤ 2.000.000.000

Exemplu

Intrare

1100

Ieșire

2 2 5 5 11

Explicație

Numărul n=1100=2*2*5*5*11.

Rezolvare

<syntaxhighlight lang="python" line> import math

def validare_date(date):

   try:
       n = int(date)
       if n >= 2 and n <= 2000000000:
           return n
       else:
           print("Numarul introdus trebuie sa fie un numar natural intre 2 si 2.000.000.000")
           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 <= math.sqrt(n):
           if n % i == 0:
               print(i, end=' ')
               n //= i
           else:
               i += 1

       if n > 1:
           print(n, end=' ')
       
       print("\nDatele de intrare corespund restricțiilor impuse.\n")
   else:
       print("Datele de intrare nu corespund restricțiilor impuse.")

</syntaxhighlight>

Explicație rezolvare

Acest cod realizează factorizarea în factori primi a unui număr natural dat de utilizator. Factorizarea în factori primi reprezintă descompunerea unui număr natural în produsul de numere prime.

Codul începe prin definirea funcției validare_date, care primește un argument date și încearcă să convertască acest argument la un număr întreg folosind funcția int(). Dacă conversia este posibilă și numărul este mai mare sau egal cu 2 și mai mic sau egal cu 2.000.000.000, atunci funcția returnează acest număr. În caz contrar, funcția afișează un mesaj corespunzător și returnează valoarea None.

După definirea funcției validare_date, codul verifică dacă acesta este rulat ca program principal folosind instrucțiunea if name == 'main':. În caz afirmativ, utilizatorului i se cere să introducă numărul n prin intermediul funcției input(). Apoi, valoarea introdusă este validată prin apelarea funcției validare_date.

Dacă valoarea introdusă este validă, codul continuă să factorizeze numărul în factori primi. În acest scop, este folosită o buclă while care parcurge valorile între 2 și radicalul numărului dat (inclusiv). Dacă numărul dat este divizibil cu valoarea curentă a buclei, atunci această valoare reprezintă un factor prim și este afișată. De asemenea, numărul dat este împărțit la acest factor. Dacă numărul dat nu este divizibil cu valoarea curentă a buclei, atunci valoarea curentă este incrementată cu 1.

După ce bucla se termină, numărul dat trebuie să fie un număr prim sau să fie egal cu 1 (deoarece toți ceilalți factori primi au fost deja afișați). Dacă numărul dat este mai mare decât 1, atunci acesta este afișat.

În cele din urmă, este afișat un mesaj corespunzător care indică dacă datele introduse de utilizator corespund restricțiilor impuse de funcția validare_date.