1020 - Mat Prim

Cerința

Se consideră un șir cu n elemente, numere naturale. Folosind metoda Divide et Impera, determinați cel mai mare element prim din acest șir.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi cele n elemente ale șirului.

Date de ieșire

Programul va afișa pe ecran numărul M, cel mai mare element prim al șirului.

Restricții și precizări

• 1 ≤ n ≤ 1000
• elementele șirului vor fi mai mici decât 1.000.000
• se garantează că în șir apare cel puțin un element prim
• se recomandă folosirea metodei Divide et Impera

Exemplul 1

Intrare

6
4 1 8 4 3 5 

Ieșire

5

Exemplul 2

Intrare

4
4 4 4 4 

Ieșire

Eroare: În șir trebuie să existe cel puțin un element prim.

Rezolvare

<syntaxhighlight lang="python3" line="1"> def este_prim(numar):

   if numar < 2:
       return False
   for i in range(2, int(numar**0.5) + 1):
       if numar % i == 0:
           return False
   return True

def gaseste_cel_mai_mare_prim(sir, stanga, dreapta):

   if stanga == dreapta:
       return sir[stanga] if este_prim(sir[stanga]) else -1

   mijloc = (stanga + dreapta) // 2

   # Caută în stânga și dreapta
   cel_mai_mare_prim_stanga = gaseste_cel_mai_mare_prim(sir, stanga, mijloc)
   cel_mai_mare_prim_dreapta = gaseste_cel_mai_mare_prim(sir, mijloc + 1, dreapta)

   # Combină rezultatele
   return max(cel_mai_mare_prim_stanga, cel_mai_mare_prim_dreapta)

def verifica_restrictii(n, sir):

   # Verifică restricția 1: 1 ≤ n ≤ 1000
   if not (1 <= n <= 1000):
       print("Nu respectă condiția lui n")
       return False

   # Verifică restricția 2: Elementele șirului vor fi mai mici decât 1.000.000
   if any(x >= 1000000 for x in sir):
       print("Eroare: Elementele șirului trebuie să fie mai mici decât 1.000.000.")
       return False

   # Verifică restricția 3: Se garantează că în șir apare cel puțin un element prim
   if all(not este_prim(x) for x in sir):
       print("Eroare: În șir trebuie să existe cel puțin un element prim.")
       return False

   return True

def main():

   # Exemplu de folosire în funcția principală
   n = int(input("Introduceti numarul de elemente: "))
   
   # Inițializează un șir gol pentru a colecta elementele
   sir = []

   # Colectează elementele șirului
   for i in range(n):
       element = int(input("Introduceti elementul {}: ".format(i + 1)))
       sir.append(element)

   # Verifică restricțiile înainte de a continua
   if not verifica_restrictii(n, sir):
       return

   # Continuă cu restul codului
   rezultat = gaseste_cel_mai_mare_prim(sir, 0, n - 1)
   print("Cel mai mare element prim din sir:", rezultat)

1. Apelul funcției principale

if __name__ == "__main__":

   main()

</syntaxhighlight>