3324 - Eratostene0
Sursa: - 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.
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.