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>

1. 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.