3319 - Eratostene8

Sursa: - Eratostene8

---

Cerinţa

Se dau n numere naturale prime. Pentru t perechi de numere naturale s şi d să se afle câte numere naturale din intervalul [s,d] sunt divizibile prin cel puţin unul dintre cele n numere prime.

Date de intrare

Fișierul de intrare eratostene8.in conține pe prima linie numerele n şi t, pe a doua linie cele n numere prime, iar pe următoarele t linii câte o pereche de numere s şi d.

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 eratostene8.out va conține pe linia i răspunsul la întrebarea i, pentru orice i de la 1 la t. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".

Restricţii şi precizări

• 1 ≤ n ≤ 10.000
• 1 ≤ t ≤ 100.000
• 1 ≤ s ≤ d ≤ 10.000.000
• numerele prime sunt mai mici sau egale cu 1.000.000

Exemple

Exemplul 1

eratostene8.in

2 3

2 3

1 5

4 6

5 20

Ieșire

Datele sunt corecte.

eratostene8.out

3

2

10

Exemplul 2

eratostene8.in

2 4

2 7

2 8

2 9

3 10

Ieșire

Datele sunt corecte.

eratostene8.out

4

4

5

Exemplul 3

eratostene8.in

2 2

2 3

191824719471 19991

314441 41241241

Ieșire

Datele nu sunt comform restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line>

1. 3319

def eratostene(vector, nr_prime):

   f = open("eratostene8.out", "w")
   for i in range(len(vector)):
       s , d = vector[i]
       total_divizibile=0
       for j in range(s,d+1):
           gasit=0
           for x in nr_prime:
               if j%x==0 and gasit==0:
                   total_divizibile+=1
                   gasit=1
       f.write(str(total_divizibile)+ "\n")
       
       

def conform_restrictiilor():

   vector = list()
   with open('eratostene8.in') as f:
       n , t  = map(int,f.readline().split())
       nr_prime=list(map(int, f.readline().split()))
       vector = []
       for line in f:
           s, d = map(int, line.split())
           vector.append((s, d))
   if n > 10000 or n < 1 or t<1 or t>100000:
       print("Datele nu sunt comform restricțiilor impuse.")
       exit()
   for s,d in vector:
       if s < 0 or s > 10000000 or d<1 or d>10000000:
           print("Datele nu sunt comform restricțiilor impuse.")
           exit()
   print("Datele sunt corecte.")
   return vector, nr_prime

if __name__ == '__main__':

   vector, nr_prime = conform_restrictiilor()
   eratostene(vector, nr_prime)

</syntaxhighlight>

Explicaţie cod

Funcția conform_restrictiilor() este utilizată pentru a verifica dacă datele din fișierul de intrare respectă restricțiile problemei. Ea deschide fișierul eratostene2.in, citește din el cele două numere de pe prima linie, n și t, primele n numere prime de pe a doua linie și apoi t perechi de numere de pe liniile următoare. Pentru fiecare pereche, funcția verifică dacă s și d se încadrează în intervalele specificate în restricții și afișează un mesaj de eroare și închide programul dacă nu se îndeplinesc aceste condiții. În cele din urmă, funcția returnează vectorul de perechi și lista numerelor prime.

Funcția eratostene() primește vectorul de perechi și lista de numere prime și calculează câte numere din fiecare interval din fiecare pereche sunt divizibile cu cel puțin unul dintre cele n numere prime date. Aceasta deschide fișierul de ieșire eratostene8.out și iterează prin fiecare pereche de numere în vector. Pentru fiecare pereche, funcția parcurge intervalul de la s la d și pentru fiecare număr din interval, se verifică dacă este divizibil cu cel puțin unul dintre numerele prime date. Dacă numărul este divizibil cu cel puțin unul dintre ele, se adaugă 1 la variabila total_divizibile. Funcția scrie valoarea total_divizibile în fișierul de ieșire pentru fiecare pereche de numere.

În funcția principală, se apelează mai întâi conform_restrictiilor() pentru a verifica datele de intrare și pentru a obține vectorul și lista de numere prime. Apoi, se apelează funcția eratostene() pentru a calcula rezultatele și pentru a scrie rezultatele în fișierul de ieșire.