2329 - prim007

Sursa: - prim007

---

Cerinţa

Se dă un șir a1, a2, …, an format din n numere naturale. Determinați numărul de perechi de elemente din șir (ai,aj) cu i < j, care au suma număr prim.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt corecte.", iar apoi va afișa pe ecran numărul rezultatelor care sunt numere prime. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".

Restricţii şi precizări

• 2 ≤ n ≤ 100.000
• elementele șirului vor fi mai mici decât 10.000

Exemple

Exemplul 1

Intrare

3

2 5 9

Ieșire

Datele sunt corecte.

2

Exemplul 2

Intrare

5

16 7 90 19 82

Ieșire

Datele sunt corecte.

5

Exemplul 3

Intrare

2

314515341535441 412351541241

Ieșire

Datele nu sunt comform restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line>

1. 2329 prim007

def este_prim(n):

   if n < 2:
       return False
   for i in range(2, int(n ** 0.5) + 1):
       if n % i == 0:
           return False
   return True

def prim007(n,vector):

   count = 0
   for i in range(n):
       for j in range(i+1, n):
           if este_prim(vector[i] + vector[j]):
               count += 1
   print(count)
   

def conform_restrictiilor(n,vctor):

   if not 2 <= n <= 100000:
       print("Datele nu sunt conform restricțiilor impuse.")
       return False
   for x in vector:
       if x > 10000:
           print("Datele nu sunt conform restricțiilor impuse.")
           return False
   print("Datele sunt corecte.")
   return True
       

if __name__ == '__main__':

   n = int(input())
   vector = list(map(int, input().split()))
   if conform_restrictiilor(n,vector) is True:
       prim007(n,vector)

</syntaxhighlight>

Explicaţie cod

Functia este_prim(n) - Verifica daca un numar este prim sau nu. Daca numarul este mai mic decat 2, functia va returna False, altfel, va verifica daca numarul are un divizor in intervalul [2, sqrt(n)]. Daca il gaseste, functia va returna False, altfel, va returna True.

Functia prim007(n, vector) - Primeste un numar n si un vector de numere vector. Functia itereaza prin toate perechile de numere din vector, calculeaza suma lor si verifica daca suma este un numar prim prin apelarea functiei este_prim(n). Daca suma este un numar prim, va incrementa un contor. La final, functia va afisa valoarea contorului.

Functia conform_restrictiilor(n, vector) - Verifica daca valorile primite ca input respecta restrictiile impuse de problema. Verifica daca n este intre 2 si 100000, iar valorile din vector sunt mai mici sau egale cu 10000. Daca valorile respecta restrictiile, functia va returna True, altfel, va afisa un mesaj de eroare si va returna False.

In functia main, programul primeste input-ul, verifica daca acesta respecta restrictiile impuse prin apelarea functiei conform_restrictiilor(n, vector) si, daca este cazul, calculeaza si afiseaza numarul de perechi de numere din vector a caror suma este un numar prim prin apelarea functiei prim007(n, vector).