3360 - Pereche 2

Cerinţa

Se dă un șir de n numere naturale. Determinați o pereche de numere consecutive în șir, cu proprietatea că au același număr de factori primi. Dacă sunt mai multe asemenea perechi se va determina aceea cu suma numerelor mai mică. Dacă în continuare sunt mai multe perechi, se va determina prima din șir.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale

Date de ieşire

Programul va afișa pe ecran două numere a b, separate prin câte un spațiu, reprezentând perechea determinată. Ordinea numerelor a b este cea din șir.

Restricții și precizări

• 1 ≤ n ≤ 1000
• numerele din șir vor fi mai mici decât 1.000.000.000
• dacă nu există nicio pereche care respectă cerința se va afișa NU EXISTA

Exemplu

Intrare

5

40 63 64 27 100

Ieșire

64 27

Explicație

Perechea 40 63 respectă regula, dar are suma mai mare (40+63 > 64 + 27).

Rezolvare

<syntaxhighlight lang="python" line> import math

def desc(n):

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

def ok(a, b):

   return desc(a) == desc(b)

def validare_date():

   while True:
       try:
           n = int(input("Introduceti numarul de elemente din sir: "))
           if n < 2:
               print("Sirul trebuie sa aiba cel putin 2 elemente.")
           else:
               break
       except ValueError:
           print("Numarul de elemente trebuie sa fie un numar intreg.")
   a = None
   while a is None:
       try:
           a = int(input("Introduceti primul element: "))
       except ValueError:
           print("Elementul trebuie sa fie un numar intreg.")
   return n, a

if __name__ == '__main__':

   n, a = validare_date()
   rez1 = 1000000000
   rez2 = 1000000000

   for i in range(2, n+1):
       b = None
       while b is None:
           try:
               b = int(input(f"Introduceti al {i}-lea element: "))
           except ValueError:
               print("Elementul trebuie sa fie un numar intreg.")

       if ok(a, b) and a + b < rez1 + rez2:
           rez1 = a
           rez2 = b
       a = b

   if rez1 != 1000000000:
       print(f"Numerele cautate sunt {rez1} si {rez2}.")
   else:
       print("NU EXISTA")

</syntaxhighlight>

Explicație rezolvare

Scopul programului este să găsească două numere consecutive dintr-un șir dat, astfel încât cele două numere să aibă același număr de factori primi, iar suma lor să fie cea mai mică posibilă.

Programul începe prin citirea numărului de elemente din șir și a primului element din șir. Datele de intrare sunt verificate și validate pentru a se asigura că sunt corecte.

Următorul pas este să căutăm perechile de numere consecutive cu același număr de factori primi. Pentru aceasta, vom itera prin șir, începând cu al doilea element, și vom verifica fiecare pereche de numere consecutive. Pentru a verifica dacă două numere au același număr de factori primi, putem folosi funcția desc(), care primește un număr și returnează numărul de factori primi ai săi. Apoi, vom compara suma celor două numere cu cele mai mici sume găsite până acum și vom actualiza cele două numere de rezultat, rez1 și rez2, dacă găsim o pereche cu o sumă mai mică.

La sfârșitul programului, dacă am găsit o pereche validă de numere, vom afișa cele două numere. În caz contrar, vom afișa "NU EXISTA".

În plus față de acest proces de găsire a perechilor, programul a fost modificat și pentru a include o funcție de validare a datelor de intrare pentru a verifica dacă numărul de elemente din șir și primul element din șir sunt introduse corect. Astfel, se evită erorile de execuție cauzate de datele de intrare incorecte.