1020 - Mat Prim
De la Universitas MediaWiki
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
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()