3353 - Factori 2

Cerinţa

Se dau două numere naturale. Afișați numărul pentru care produsul factorilor primi este mai mare. Dacă cele două numere au același produs al factorilor primi, afișați-l pe cel mai mic.

Date de intrare

Programul citește de la tastatură două numere naturale.

Date de ieşire

Programul va afișa pe ecran numărul cerut.

Restricții și precizări

• cele două numere citite vor fi mai mici decât 1.000.000.000

Exemplu

Intrare

36 26

Ieșire

26

Explicație

Factorii primi ai lui 36 sunt 2 și 3, cu produsul 6. Factorii primi ai lui 26 sunt 2 și 13, cu produsul 26. Rezultatul este 26, pentru că are produsul factorilor primi mai mare.

Rezolvare

<syntaxhighlight lang="python" line> def desc(n):

   prod = 1
   d = 2
   while n > 1:
       p = 0
       while n % d == 0:
           n //= d
           p += 1
       if p:
           prod *= d
       d += 1
       if d * d > n:
           d = n
   return prod

def validare_date(a, b):

   if a < 1 or a > 10**18 or b < 1 or b > 10**18:
       return False
   return True

if __name__ == '__main__':

   a, b = map(int, input().split())
   if validare_date(a, b):
       print("\nDatele de intrare corespund restricțiilor impuse.\n")
       prod1 = desc(a)
       prod2 = desc(b)
       if prod1 > prod2:
           print(a)
       elif prod1 == prod2:
           print(min(a, b))
       else:
           print(b)
   else:
       print("Datele de intrare nu corespund restricțiilor impuse.")

</syntaxhighlight>

Explicație rezolvare

Codul verifică dacă două numere date sunt în intervalul [1, 10^18] și calculează divizorul cel mai mic comun între ele. Pentru a face acest lucru, se utilizează o funcție care găsește factorii primi ai fiecărui număr și apoi calculează produsul lor. Dacă datele de intrare nu corespund restricțiilor impuse, programul afișează un mesaj de eroare. Altfel, programul afișează divizorul cel mai mic comun și numărul corespunzător cu cel mai mic divizor.