3317 - Eratostene6

Sursa: - Eratostene6

---

Cerinţa

Se dă un şir format din n numere naturale, a1, a2, …, an. O pereche ( ai, aj), unde i<j, se numeşte eratostenică dacă i divide pe j şi ai divide pe aj. Determinaţi câte perechi eratostenice conţine şirul dat.

Date de intrare

Fișierul de intrare eratostene6.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 eratostene6.out va conține pe prima linie numărul perechilor eratostenice din şirul dat. Î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
• 0 ≤ a1, a2, …, an ≤ 1.000

Exemple

Exemplul 1

eratostene6.in

4

2 3 0 6

Ieșire

Datele sunt corecte.

eratostene6.out

3

Exemplul 2

eratostene6.in

3

1 8 5

Ieșire

Datele sunt corecte.

eratostene6.out

2

Exemplul 3

eratostene6.in

2

191824719471 19991

Ieșire

Datele nu sunt comform restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line>

1. 3317

def eratostene(vector, n):

   f = open("eratostene6.out", "w")
   nr_perechi = 0
   for i in range(1, n//2+1):
       for j in range(i*2, n+1, i):
           if vector[i-1] != 0 and vector[j-1] % vector[i-1] == 0:
               nr_perechi += 1
           elif vector[i-1] == 0 and vector[j-1] == 0:
               nr_perechi += 1
   f.write(str(nr_perechi))

def conform_restrictiilor():

   vector = list()
   with open('eratostene6.in') as f:
       n = int(f.readline())
       vector = list(map(int, f.readline().split()))
   if n > 500000 and n < 1:
       print("Datele nu sunt comform restricțiilor impuse.")
       exit()
   for x in vector:
       if x < 0 or x > 1000:
           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

Funcția conform_restrictiilor() este folosită pentru a citi datele de intrare din fișierul eratostene6.in și pentru a verifica dacă acestea respectă restricțiile impuse în cerință. În cazul în care datele nu respectă restricțiile, programul se oprește prin utilizarea funcției exit().

Funcția principală, eratostene(vector, n), primește ca argumente vectorul de numere și dimensiunea sa și calculează numărul de perechi eratostenice. Algoritmul este bazat pe două bucle for care parcurg toate perechile de indici i și j, respectând condiția i<j.

În interiorul buclei, se verifică dacă i divide j și dacă a[i] divide a[j]. În caz afirmativ, se incrementează contorul nr_perechi. Pentru a evita eroarea de împărțire la zero, se verifică, de asemenea, dacă a[i] sau a[j] este egal cu zero.

La sfârșit, numărul de perechi eratostenice este scris în fișierul eratostene6.out.