1832 - Pd

Cerința

Se dă un număr natural s. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe s ca produs de divizori proprii distincți ai lui s.

Date de intrare

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

Date de ieșire

Programul va afișa pe ecran pe fiecare linie câte un şir de numere naturale ordonate strict crescător, separate prin câte un spaţiu. Produsul numerelor din fiecare şir este s, iar numerele sunt divizori proprii ai lui s. Şirurile vor fi afişate în ordine lexicografică.

Dacă numărul s nu poate fi scris ca produs de divizori proprii, se va fişa mesajul NU EXISTA.

Restricții și precizări

• 2 ≤ s ≤ 2000000000

Exemplu 1

Intrare

30

Iesire

2 3 5
2 15
3 10
5 6

Rezolvare

<syntaxhighlight lang="python" line> from itertools import combinations import math

def find_divisors(n):

   divisors = []
   for i in range(2, int(math.sqrt(n)) + 1):
       if n % i == 0:
           divisors.append(i)
           if i != n // i:
               divisors.append(n // i)
   divisors.sort()
   return divisors

def find_combinations(divisors, s):

   result = []
   for i in range(1, len(divisors) + 1):
       for combo in combinations(divisors, i):
           product = 1
           for num in combo:
               product *= num
           if product == s:
               result.append(combo)
   return result

def main():

   s = int(input().strip())

   if s <= 1:
       print("NU EXISTA")
       return

   divisors = find_divisors(s)
   combinations = find_combinations(divisors, s)

   if not combinations:
       print("NU EXISTA")
   else:
       sorted_combinations = sorted(combinations)
       for combo in sorted_combinations:
           print(" ".join(map(str, combo)))

if __name__ == "__main__":

   main()

</syntaxhighlight>