View source for 1020 - Mat Prim

= Cerința =
Se consideră un șir cu <code>n</code> 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 <code>n</code>, iar apoi cele <code>n</code> elemente ale șirului.

= Date de ieșire =
Programul va afișa pe ecran numărul <code>M</code>, cel mai mare element prim al șirului.

= Restricții și precizări =

* <code>1 ≤ n ≤ 1000</code>
* elementele șirului vor fi mai mici decât <code>1.000.000</code>
* 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)

# Apelul funcției principale
if __name__ == "__main__":
    main()

</syntaxhighlight>