Editing 3324 - Eratostene0

Sursa: [https://www.pbinfo.ro/probleme/3324/eratostene0 - Eratostene0]
----
== Cerinţa ==
Se dau '''n''' perechi de numere naturale '''(i, j)''', cu '''i ≤ j'''. Pentru fiecare pereche trebuie să aflați '''suma''' divizorilor tuturor numerelor din șirul i, i + 1, ..., j.
== Date de intrare ==
Fișierul de intrare '''eratostene0.in''' conține pe prima linie numărul '''n''', iar pe următoarele n linii câte două numere naturale i(1) j(1), i(2) j(2), …, i(n) j(n).
== 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 '''eratostene0.out''' va conține '''n''' linii, pe fiecare linie L, L = 1..n, aflându-se un singur număr natural reprezentând suma divizorilor tuturor numerelor corespunzătoare perechii '''i(L) j(L)'''. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".

== Restricţii şi precizări ==
* 1 ≤ '''n''' ≤ 200.000
* 1 ≤ '''i''' ≤ '''j''' ≤ 1.000.000
== Exemple ==
===Exemplul 1===
; eratostene0.in
: 4
: 1 6
: 3 7
: 2 5
: 8 8
; Ieșire
: Datele sunt corecte.
; eratostene0.out
: 33
: 37
: 20
: 15
===Exemplul 2===
; eratostene0.in
: 3
: 2 4
: 10 20
: 40 90
; Ieșire
: Datele sunt corecte.
; eratostene0.out
: 14
: 270
: 5481
===Exemplul 3===
; eratostene0.in
: 2
: 191824719471 19991
: 120 200
; Ieșire
: Datele nu sunt comform restricțiilor impuse.
<br>
== Rezolvare == 
<syntaxhighlight lang="python" line>
#3324 Eratostene0

def eratostene(vector, n):
    suma = 0
    f = open("eratostene0.out", "w")
    for k in range(0, n * 2, +2):
        suma = 0
        i = vector[k]
        j = vector[k + 1]
        for numar in range(i, j + 1):
            divizor = 1
            while divizor <= numar:
                if numar % divizor == 0:
                    suma += divizor
                divizor += 1
        f.write(str(suma) + "\n")


def conform_restrictiilor():
    vector = list()
    with open('eratostene0.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 > 200000 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 calculează suma divizorilor pentru intervale de numere date în fișierul '''eratostene0.in''' și scrie sumele corespunzătoare în fișierul '''eratostene0.out'''.

Funcția '''conform_restrictiilor()''' citeste datele din fișier și verifică dacă sunt în limitele impuse de restricțiile problemei. Apoi, returnează numerele citite din fișier într-un vector și numărul de intervale de numere.

Funcția '''eratostene()''' primește vectorul și numărul de intervale de numere ca parametri. Apoi, pentru fiecare interval de numere, calculează suma divizorilor pentru fiecare număr în interval și o scrie în fișierul de ieșire.

Spre deosebire de numărul prim, suma divizorilor unui număr nu poate fi determinată cu un algoritm eficient. De aceea, se verifică fiecare divizor de la 1 la numărul în cauză și se adaugă la suma dacă divizează numărul.