1149 - Exista Prime Div Imp
De la Universitas MediaWiki
Cerinţa
Se dă un şir cu n
elemente, numere naturale. Folosind metoda Divide et Impera să se verifice dacă în şir există elemente prime.
Date de intrare
Programul citește de la tastatură numărul n
, iar apoi cele n
elemente ale şirului.
Date de ieşire
Programul afișează pe ecran mesajul DA
, dacă şirul conţine elemente prime, respectiv NU
în caz contrar.
Restricţii şi precizări
1 ≤ n ≤ 200
- elementele şirului vor fi mai mici decât
1.000.000.000
Exemplul 1
Date de intrare
5 21 8 6 10 8
Date de ieșire
NU
Exemplul 2
Date de intrare
2000
Date de ieșire
Eroare: Numărul de elemente trebuie să fie între 1 și 200.
Rezolvare
def is_prime(num):
if num < 2:
return False
for i in range(2, int(num ** 0.5) + 1):
if num % i == 0:
return False
return True
def has_prime_elements(arr, start, end):
if start == end:
return is_prime(arr[start])
mid = (start + end) // 2
left_has_prime = has_prime_elements(arr, start, mid)
right_has_prime = has_prime_elements(arr, mid + 1, end)
return left_has_prime or right_has_prime
def validate_input(n):
if not (1 <= n <= 200):
print("Eroare: Numărul de elemente trebuie să fie între 1 și 200.")
exit()
def main():
n = int(input("Introduceți numărul de elemente: "))
validate_input(n)
arr = []
for i in range(n):
element = int(input(f"Introduceți elementul {i + 1}: "))
arr.append(element)
if has_prime_elements(arr, 0, n - 1):
print("DA")
else:
print("NU")
if __name__ == "__main__":
main()