3525 - soft prime

Cerinţa

Se dă un şir format din n numere naturale nenule distincte. Afişaţi numerele prime din şir, în ordine crescătoare.

Date de intrare

Fișierul de intrare soft_prime.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale nenule distincte, 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 soft_prime.out va conține pe prima linie numerele prime din şirul dat, scrise în ordine crescătoare. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".

Restricţii şi precizări

1 ≤ n ≤ 40.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

Exemple

Exemplul 1

soft_prime.in: 5; 13 9 31 79 23
Ieșire: Datele sunt corecte.
soft_prime.out: 13 23 31 79

Exemplul 2

soft_prime.in: 5; 2 13 11 19 8
Ieșire: Datele sunt corecte.
soft_prime.out: 2 11 13 19

Exemplul 3

soft_prime.in: 2; 314441 41241241
Ieșire: Datele nu sunt comform restricțiilor impuse.

Rezolvare

3525

def soft_prime(vector, n):

    f = open("soft_prime.out", "w")
   nr_prime = list()
   for numar in vector:
       if numar < 2 or numar % 2 == 0 and numar != 2:
           break
       divizor = 3
       while divizor * divizor <= numar:
           if numar % divizor == 0:
               break
           divizor += 2
       if divizor ** 2 > numar:
           nr_prime.append(numar)
   nr_prime.sort()
   for i in nr_prime:
       f.write(str(i)+ " ")

def conform_restrictiilor():

   vector = list()
   with open('soft_prime.in') as f:
       n = int(f.readline())
       vector=list(map(int, f.readline().split()))
   if n > 40000 or n < 1:
       print("Datele nu sunt comform restricțiilor impuse.")
       exit()
   for x in vector:
       if x<0 or x>1000000:
           print("Datele nu sunt comform restricțiilor impuse.")
           exit()
   print("Datele sunt corecte.")
   return vector, n

if __name__ == '__main__':

   vector, n = conform_restrictiilor()
   soft_prime(vector, n)

</syntaxhighlight>

Explicaţie cod

Funcția soft_prime(vector, n) primește ca parametri un vector de n elemente și determină numerele prime din el. În primul rând, se deschide un fișier nou, numit soft_prime.out în care vor fi scrise numerele prime găsite. Apoi, se parcurge vectorul și pentru fiecare element, se verifică dacă este egal cu 2, caz în care este adăugat direct în lista de numere prime nr_prime. Dacă elementul nu este 2, se calculează primii divizori ai săi prin împărțirea succesivă cu numerele impare mai mari sau egale decât 3. Dacă se găsește un divizor, atunci numărul nu este prim și se trece la următorul element din vector. Dacă nu s-a găsit niciun divizor mai mic sau egal cu radicalul pătrat al numărului, atunci numărul este prim și este adăugat în lista de numere prime. La final, lista de numere prime este sortată crescător și fiecare element este scris în fișierul de ieșire, separat prin spații.

Funcția conform_restrictiilor() deschide fișierul de intrare soft_prime.in și citește dimensiunea vectorului și elementele sale. Apoi, se verifică dacă valorile citite respectă restricțiile impuse de enunț, adică n trebuie să fie între 1 și 40000, iar elementele vectorului trebuie să fie numere naturale mai mici sau egale cu 1000000. Dacă datele sunt corecte, funcția returnează vectorul și dimensiunea sa.

În funcția principală main(), se apelează mai întâi funcția conform_restrictiilor() pentru a citi datele din fișierul de intrare și a verifica dacă sunt valide. Apoi, se apelează funcția soft_prime() pentru a determina numerele prime din vectorul citit și a le scrie în fișierul de ieșire.