0496 - Numarare4

Sursa: 0496 - Numarare4

---

Cerinţa

Se dă un vector cu n numere naturale. Să se determine câte dintre elementele vectorului sunt prime cu ultimul element.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spaţii, reprezentând elementele vectorului.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou afișează pe ecran numărul C, reprezentând valoarea cerută.. În cazul în care datele nu respectă restricțiile, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• 1 ⩽ n ⩽ 200
• elementele vectorului vor fi cuprinse între 0 și 1.000

Exemple

Exemplul 1

Intrare

6

50 64 15 28 35 75

Ieșire

Datele sunt introduse corect.

2

Explicație exemplu 1

Elementele din vector prime cu 75 sunt 64 și 28.

Exemplul 2

Intrare

5

10 2 -3 4 5

Ieșire

Datele nu corespund restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line>

1. 0496

def nr_elem_prime_cu_ultimul(vector, n):

   ultimul_element = vector[n-1]
   numar_elemente_prime = 0
   for element in vector:
       limita_superioara = int(element**0.5) + 1
       nr_divizori_comuni = 0
       for divizor in range(3, limita_superioara, 2):
           if element % divizor == 0:
               nr_divizori_comuni += 1
       if nr_divizori_comuni == 0:
           numar_elemente_prime += 1
   print(numar_elemente_prime)

def citire_conform_restrictiilor(vector, n):

   if n < 1 or n > 200:
       print("Datele nu corespund restricțiilor impuse.")
       exit()
   for x in vector:
       if x < 0 or x > 1000:
           print("Datele nu corespund restricțiilor impuse.")
           exit()
   if n != len(vector):
       print("Datele nu corespund restricțiilor impuse.")
       exit()
   print("Datele sunt introduse corect.")

if __name__ == '__main__':

   n = int(input())
   vector = list(map(int, input().split()))
   citire_conform_restrictiilor(vector, n)
   nr_elem_prime_cu_ultimul(vector, n)

</syntaxhighlight>

Explicație rezolvare

  În programul de mai sus se definesc două funcții, funcția nr_elem_prime_cu_ultimul(vector, n) și funcția citire_conform_restrictiilor(vector, n), care vor fi apelate în interiorul secțiunii if __name__ == '__main__':(liniile 34, 35), după citirea numărului n și celor n numere pe care le vom pune în vectorul "vector" (liniile 32, 33). 
   În funcția numită citire_conform_restrictiilor(vector, n) se asigură că input-ul îndeplinește restricțiile (numărul de elemente n este între 1 și 200, iar elementele vectorului sunt între 0 și 1000) și că numărul de elemente este egal cu n. Dacă oricare dintre condiții nu este respectată, atunci se afișează mesajul "Datele nu corespund restricțiilor impuse." și programul se oprește prin apelul funcției "exit()".
   Funcția nr_elem_prime_cu_ultimul(vector, n) primește vectorul și lungimea acestuia și apoi parcurge fiecare element din vector cu un for loop. Pentru fiecare element, se calculează limita superioară, adică rădăcina pătrată a elementului, plus 1 (avem nevoie de limita superioară pentru a verifica în mod eficient divizorii numerelor, fără a verifica toate numerele până la numărul respectiv). Apoi se parcurg toate numerele impare de la 3 până la limita superioară și se verifică dacă elementul este divizibil cu ele. Dacă nu este divizibil cu niciunul dintre acești divizori, atunci numărul este considerat prim și se incrementează numărul de elemente prime găsite, dar dacă ultimul element este 1, toate elementele din vector nu vor fi prime între ele, așadar numar_elemente_prime va fi 0. În cele din urmă, programul afișează numărul de elemente prime găsite.