3316 - Eratostene5

Sursa: - Eratostene5

---

Cerinţa

Se dau n numere naturale nenule şi se notează cu P produsul acestora. Să se afle numerele prime din descompunerea lui P în factori primi, precum şi exponentul acestora.

Date de intrare

Fișierul de intrare eratostene5.in conține pe prima linie numărul n, iar pe a doua linie 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 in fişierul de ieșire eratostene5.out va conține pe fiecare linie un număr prim din descompunerea lui P şi exponentul acestuia. Factorii primi se vor afişa î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 ≤ 500.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

Exemple

Exemplul 1

eratostene5.in

4

6 10 21 56

Ieșire

Datele sunt corecte.

eratostene5.out

2 5

3 2

5 1

7 2

Exemplul 2

eratostene5.in

3

1 8 5

Ieșire

Datele sunt corecte.

eratostene5.out

2 3

5 1

Exemplul 3

eratostene5.in

2

191824719471 19991

Ieșire

Datele nu sunt comform restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line>

1. 3316

def eratostene(vector, n):

   numere_prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
   f = open("eratostene5.out", "w")
   P = 1
   for x in vector:
       P *= x
   factori_primi = 0
   for j in numere_prime:
       if P == 1:
           break
       elif P % j == 0:
           numar_factori_primi = 0
           factori_primi = j
           while P % j == 0:
               P //= j
               numar_factori_primi += 1
       f.write(str(factori_primi) + " "+ str(numar_factori_primi)+ "\n")

def conform_restrictiilor():

   vector = list()
   with open('eratostene5.in') as f:
       lines = f.readlines()
       for line in lines:
           for c in line.split():
               if c.isdigit() == True:
                   vector.append(int(c))
   n = vector[0]
   vector = vector[1:]
   if n > 500000 and 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()
   eratostene(vector, n)

</syntaxhighlight>

Explicaţie cod

Acest cod primește un fișier de intrare eratostene5.in care conține un număr n urmat de n numere întregi. Scopul programului este de a calcula numărul de factori primi ai produsului numerelor din vectorul de intrare și să afișeze acești factori primi și numărul lor de apariții într-un fișier de ieșire numit eratostene5.out.

Funcția conform_restrictiilor citeste din fișierul de intrare și validează datele. Dacă datele nu respectă restricțiile de numărul maxim și minim pentru n și valorile numerelor din vector, programul se oprește. În caz contrar, vectorul este returnat împreună cu n pentru a fi procesat în funcția eratostene.

Funcția eratostene calculează produsul numerelor din vectorul de intrare și numărul de factori primi ai acestui produs. Apoi, funcția parcurge lista de numere prime și verifică dacă produsul numerelor din vector se divide exact cu numărul prim curent. Dacă acest lucru este adevărat, atunci funcția calculează numărul de apariții ale factorului prim respectiv în produs, utilizând o buclă while. Apoi, funcția scrie factorul prim și numărul său de apariții în fișierul de ieșire.