1149 - Exista Prime Div Imp

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

<syntaxhighlight lang="python3" line="1"> 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()

</syntaxhighlight>