Vizualizare sursă pentru „3317 - Eratostene6”

Sursa: [https://www.pbinfo.ro/probleme/3317/eratostene6 - 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.
<br>
== Rezolvare == 
<syntaxhighlight lang="python" line>
#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(sdef eratostene(vector, n):
    f = open("out.txt", "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'''.