Clasa a V-a lecția 33 - 04 apr 2020

From Algopedia
Jump to navigationJump to search

Lecție

Nu există video. Lecția este doar teoretică și disponibilă online.

Ciurul lui Eratostene

Eratostene a fost un matematician, geograf, poet, astronom și muzician grec. El a trăit între anii 276 și 195 î.Hr. El a inventat cuvîntul "geografie" în greacă, a inventat un sistem de latitudine și longitudine. A fost primul om care a calculat circumferința pămîntului, a calculat înclinația axei de rotație a pămîntului, a creat conceptul de an bisect, și zi bisectă. Tot el a creat prima hartă a lumii, incluzînd paralele și meridiane.

Eratostene a inventat un algoritm foarte eficient de calcul al tuturor numerelor prime pînă la un număr dat. Acest algoritm se studiază la matematică. El procedează astfel:

  1. Creează o listă a întregilor consecutivi de la 2 la n: [2, 3, 4, ..., n].
  2. Caută primul număr netăiat din listă (inițial nici un număr nu e tăiat). Fie p acel număr.
  3. Mergi din p în p prin listă, începînd cu 2*p și taie toate numerele întîlnite (unele vor fi deja tăiate)
  4. Reia de la pasul 2, pînă ce depășim n.

În final numerele rămase netăiate sînt prime. Pentru o exemplificare mai bună, puteți urmări următorul video:

Cum implementăm acest algoritm, care la origine se executa manual, cu hîrtie și creion? Pentru a simula tăierea numerelor vom folosi un vector de frecvență, ciur, care pentru fiecare număr între 2 și n ne va spune dacă este tăiat sau nu. Inițial vectorul ciur va fi inițializat cu zero, care semnifică că toate numerele sînt prime, iar pe măsură ce tăiem numere, ele vor fi marcate cu unu. În final ciur[x] va fi zero dacă numărul este prim, sau unu în caz contrar. Deoarece elementele lui ciur sînt zero sau unu nu are rost să folosim întregi pentru ele, ci vom folosi caractere, văzute ca numere mici. Să ne reamintim că un caracter ocupă un octet (opt biți), pe cînd un întreg ocupă 4 octeți (32 de biți). Astfel, memoria folosită va fi de patru ori mai mică. (Vom vedea, în viitor, că memoria se poate reduce în continuare dacă ținem doar un bit pe element.)

Iată implementarea acestei idei. Programul următor calculează vectorul ciur pentru numerele pînă la n, cu n maxim două milioane:

char ciur[2000001];
...
fscanf( fin, "%d", &n );
for ( d = 2; d < n; d++ )
  if ( ciur[d] == 0 ) // daca d este prim
    for ( i = d + d; i <= n; i = i + d ) // vom marca numerele din d in d
      ciur[i] = 1;

Programul se poate optimiza dacă facem următoarele observații:

  1. În a doua buclă for variabila i ia valorile 2∙d, 3∙d, 4∙d, ..., k∙d. Pentru k < d toate valorile de forma k∙d au fost deja tăiate de valorile k anterioare, drept pentru care nu are rost să le mai parcurgem. Putem să pornim cu i de la d∙d.
  2. Conform observației anterioare i pornește de la d∙d. De aceea nu are rost să mergem cu d mai departe de sqrt(n), deoarece nu vom mai găsi i astfel încît i ≤ n.

Iată implementarea optimizată, bazată pe aceste două observații:

char ciur[2000001];
...
fscanf( fin, "%d", &n );
for ( d = 2; d * d <= n; d++ )
  if ( ciur[d] == 0 ) // daca d este prim
    for ( i = d * d; i <= n; i = i + d ) // vom marca numerele din d in d
      ciur[i] = 1;

Nu uitați! Iată erorile frecvente în implementarea ciurului lui Eratostene:

  • Vectorul ciur este un vector de caractere, nu de întregi.
  • Vectorul ciur se declară cu un element în plus față de n. Dacă n este 20000 vom declara char ciur[20001].

Adaptări ale ciurului lui Eratostene

Ciurul lui Eratostene poate fi modificat pentru a calcula și alte valori utile, nu doar primalitatea numerelor. În general, adaptările vor avea la bază prima formă a ciurului, cea neoptimizată.

Numărul de divizori primi

Putem adapta algoritmul pentru a calcula numărul de divizori primi ai numerelor de la 1 la n. Tot ce avem de făcut este ca în loc de a seta pe unu numerele din d în d, să adunăm 1 la acele elemente. Va trebui să folosim varianta neoptimizată și va trebui să pornim cu i chiar de la d și nu de la d+d.

Numărul de divizori

Putem adapta algoritmul pentru a calcula numărul de divizori (primi sau neprimi) ai numerelor de la 1 la n. Va trebui să folosim tot varianta neoptimizată și vom "tăia" numerele chiar și pentru numere neprime. La "tăiere" vom aduna unu elementului din vector, întocmai ca la varianta anterioară. Atenție, deoarece numărul de divizori poate fi mare, vectorul ciur va trebui declarat de întregi și nu de caractere.

Temă

Tema 33: să se rezolve următoarele probleme (program C trimis la vianuarena):

  • prime ca exercițiu de ciurul lui Eratostene
  • apropiate1 dată la ONI 2004 clasa a 6a, tot ca exercițiu de ciurul lui Eratostene
  • kdiv ca aplicație (variație) a ciurului lui Eratostene

Rezolvări aici [1]