0302 - CautaPrim

Sursa: - CautaPrim

---

Cerinţa

Se dau n numere naturale cu cel mult două cifre fiecare. Determinaţi cel mai mare număr prim de două cifre care nu apare printre numerele date.

Date de intrare

Fișierul de intrare cautaprim.in conţine pe prima linie numărul n; urmează cele n numere, dispuse pe mai multe linii şi separate prin spaţii.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt corecte.", iar apoi in fișierul de ieşire cautaprim.out va conţine pe prima linie cel mai mare număr prim de două cifre care nu apare printre numerele date. Dacă printre numerele date se află toate numerele prime de două cifre, în fişier se va scrie valoarea 0. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".

Restricţii şi precizări

• 1 ≤ n ≤ 100.000

Exemple

Exemplul 1

cautaprim.in

8

3 19 3 65 3 97 14 3

Ieșire

Datele sunt corecte.

cautaprim.out

89

Exemplul 2

cautaprim.in

2

97 89

Ieșire

Datele sunt corecte.

cautaprim.out

83

Exemplul 3

cautaprim.in

2

314441 41241241

Ieșire

Datele nu sunt comform restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line>

1. 0302 CautaPrim

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 cautaprim(vector):

   f = open("cautaprim.out","w")
   for p in range(97, 10, -1):
       if este_prim(p) and p not in vector:
           f.write(str(p))
           return
   f.write("0")
   
   

def conform_restrictiilor():

   with open('cautaprim.in') as f:
       n = int(f.readline().strip())
       vector = set(map(int, f.read().split()))
   if not 1 <= n <= 100000:
       print("Datele nu sunt conform restricțiilor impuse.")
       exit()
   for x in vector:
       if x > 99:
           print("Datele nu sunt conform restricțiilor impuse.")
           exit()
   print("Datele sunt corecte.")
   return n, vector 

if __name__ == '__main__':

   n, vector= conform_restrictiilor()
   cautaprim(vector)

</syntaxhighlight>

Explicaţie cod

Funcția este_prim(n) primește un număr natural n și returnează True dacă n este prim și False în caz contrar. Funcția verifică dacă n este mai mic decât 2, caz în care returnează False. Pentru a verifica dacă n este prim, funcția parcurge numerele de la 2 până la radicalul din n și verifică dacă n se divide exact la vreunul dintre ele. Dacă găsește un astfel de număr, atunci n nu este prim și se returnează False. Dacă nu se găsește niciun număr care să divizibil cu n, atunci n este prim și se returnează True.

Funcția cautaprim(vector) primește un vector de numere și găsește cel mai mare număr prim de două cifre care nu apare în vector. Funcția deschide fișierul cautaprim.out în modul de scriere ("w") și parcurge numerele prime de două cifre de la 97 la 10, în ordine descrescătoare. Dacă găsește un astfel de număr care nu apare în vector, atunci îl scrie în fișier și returnează. Dacă nu găsește un astfel de număr, atunci scrie 0 în fișier.

Funcția conform_restrictiilor() verifică dacă datele din fișierul de intrare sunt conforme cu restricțiile problemei. Funcția deschide fișierul cautaprim.in și citește prima linie, care conține numărul n de numere care urmează să fie citite. Apoi, citeste cele n numere și le pune într-un set vector. Dacă numărul n nu se află în intervalul [1, 100000] sau există cel puțin un număr din vector care este mai mare decât 99, atunci funcția afișează un mesaj corespunzător și încheie programul. În caz contrar, funcția afișează mesajul "Datele sunt corecte." și returnează tuplul (n, vector).

În blocul principal, se apelează funcția conform_restrictiilor() pentru a obține n și vectorul vector. Apoi, se apelează funcția cautaprim(vector) pentru a găsi cel mai mare număr prim de două cifre care nu apare în vector.