Clasa a IX-a lecția 25

From Algopedia
Jump to navigationJump to search

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.

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[2000000];
...
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[2000000];
...
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;

Lectie

Varianta usor optimizata

Pentru un numar d prim, vom marca toti multiplii acestuia, nepari Ex: pentru d = 7, marcam multiplii: 7*7, 7*9, 7*11...sarind peste 7*8, 7*10...

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

Putem de asemenea sa optimizam si memoria folosita, pastrand valorile ciurului doar pentru elementele impare.

ciur[1] va retine daca 3 e prim ciur[2] va retine daca 5 e prim ciur[3] va retine daca 7 e prim ciur[d/2] va retine daca d e prim Adica: ciur[k] va retine daca 2k + 1 e prim

char ciur[2000000];
for ( d = 3; d * d <= n; d+= 2 )
  if ( ciur[d/2] == 0 ) // daca d este prim
    for ( i = d * d; i <= n; i = i + 2 * d ) 
      ciur[i/2] = 1;

Nu uitați:

  • Vectorul ciur[] este de tip caracter și nu întreg!
  • În final vectorul ciur[i] este 0 dacă numărul este prim sau 1 în caz contrar.

Complexitate? Matematica este complexă, dar rețineți că metoda este aproximativ O(n) pentru valorile lui n cu care vom lucra noi. Pentru cei interesați, complexitatea este de fapt O(n∙log log n).

Utilizarea Ciurului lui Eratostene

Calcului numarului de divizori

Putem modifica modul de parcurgere al vectorului pentru a calcula numarul de divizori pentru numerele de la 1 la n:

int num_div[2000000];
...
fscanf( fin, "%d", &n );
for ( d = 1; d <= n; d++ )
  for ( i = d; i <= n; i = i + d )
    num_div[i]++;

De asemenea putem calcula similar suma divizorilor pentru numerele de la 1 la n:

int sum_div[2000000];
...
fscanf( fin, "%d", &n );
for ( d = 1; d <= n; d++ )
  for ( i = d; i <= n; i = i + d )
    sum_div[i] = sum_div[i] + d;

Construirea unui vector de numere prime ( Compactarea ciurului )

Dorim sa contruim un vector de numere prime mai mici sau egale cu o valoare data VMAX. Ne vom folosi deci de ciurul lui Eratostene pentru a determina care numere sunt prime pana la VMAX. Vom ignora numerele pare atunci cand marchez numerele neprime, neaccesand nicioadata aceste pozitii. Vom marca penru un divizor d divizorii acestuia impari: d * d, d*(d+2), sarind peste elementele d*(d+1), d*(d+3) acestea fiind numere pare.

#define VMAX 1000000
char ciur[VMAX+1] = {0}; 
int prime[300000];  // dimensiunea vectorului este data de numarul de numere prime pe care le-as putea gasi pena la VMAX

int main(){
  ................. 
  // marcam in ciur numerele impare prime
  for(int d = 3; d * d <= VMAX; d +=2 )
    if( ciur[d] == 0 )                                                 
      for(int i = d * d; i<= VMAX; i = i + 2 * d )   
        ciur[i] = 1;
  // punem nr 2 in vectorul de numere prime, fiind singurul nr par prim
  prime[0] = 2; 
  // parcurgem ciurul doar pe pozitiile impare si construim vectorul de numere prime
  k = 1;
  for( d = 3; d <= VMAX; d += 2 )
    if( ciur[d] == 0 ) 
       prime[k++] = d;
...................
}


#define VMAX 1000000

char ciur[VMAX] = {0}; 
int prime[300000];         

  v[0] = 2; k = 1;
  for(d = 3; d <= 1000000; d +=2 )
    if( ciur[d] == 0 ){                                       // daca d e prim
      prime[k++] = d;                                         // pun val d in vectorul v
      for(long long i = 1LL * d * d; i<= 1000000; i=i+2*d )   // marchez ca neprime
        ciur[i] = 1;
    }


https://infoarena.ro/problema/divprim

Temă

Tema Teorie

Tema 23 de pe pbinfo

Tema Laborator

Rezolvati problemele din runda de pe varena:

Ciur

Ciur, Compactare Ciur

  • prime, campion2005 (inca nu e pusa pe varena)
  • sprime, XOR 2015 clasa a 9 a

Ciur modificat

  • kdiv aplicație a ciurului lui Eratostene - folosim ciurul pentru a memora pentru fiecare numar cati divizori primi are fiecare numar
  • intervale aplicație a ciurului lui Eratostene - folosim ciurul pentru a memora pentru fiecare numar cati divizori primi are fiecare numar + sume partiale
  • Prime1 - pbinfo oni 2017 clasa a v-a ca aplicație a ciurului lui Eratostene; folosim ciurul pentru a marca ce numere sunt si prime si in sirul lui fibbonacci

Optional

  • prim dată la ONI 2003 clasa a 5a
  • cub1 dată la ONI 2002 clasa a 5a