Clasa a V-a lecția 6 S23
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:
- Creează o listă a întregilor consecutivi de la 2 la n: [2, 3, 4, ..., n].
- Caută primul număr netăiat din listă (inițial nici un număr nu e tăiat). Fie p acel număr.
- Mergi din p în p prin listă, începînd cu 2*p și taie toate numerele întîlnite (unele vor fi deja tăiate)
- 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:
- Î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.
- 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;Căutare binară
Căutarea binară este un mod mai rapid de a căuta pe ce poziție se află un element într-un vector.
Ce complexitate are căutarea clasică a unui element într-un vector? Deoarece elementul se poate afla pe orice poziție în vector, iar noi căutăm liniar elementele, unul după altul, rezultă că, pe medie, vom face n / 2 comparații atunci cînd elementul se află în vector. Aceasta înseamnă o complexitate de O(n). Putem să rezolvăm această problemă mai rapid?
Putem, cu condiția ca vectorul să fie ordonat. Să ne folosim de o analogie: cum căutam un cuvînt în dicționar? Dicționarul are circa 60000 de cuvinte. Dacă am căuta la rînd, liniar, ne-ar lua zile să-l găsim. Și atunci deschidem dicționarul undeva, să spunem la mijloc. Ne uităm la ce literă sîntem, să spunem 'm'. Dacă noi căutăm 'gorilă', știm că 'g' < 'm', deci vom căuta la stînga, eliminînd jumate din dicționar. Vom continua la fel, deschidem undeva la jumate în jumatea rămasă și vedem iarăși la ce literă sîntem. Atunci cînd ajungem la litera 'g' vom continua cu a doua literă. În acest fel vom găsi cuvîntul rapid, probabil în jumate de minut, în loc de zile.
Aceasta este metoda căutării binare. Dacă vectorul nostru este ordonat, putem căuta mai întîi la jumate. Dacă elementul din vector este mai mic decît elementul căutat înseamnă că trebuie să ne uităm în jumătatea dreaptă, altfel ne uităm în cea stîngă. Apoi, în vectorul rămas, vom repeta algoritmul. La fiecare pas vom înjumătăți numărul de numere rămase. Ne oprim atunci cînd subvectorul rămas are fix un element. Dacă este elementul căutat, returnăm poziția sa, altfel el nu există. Iată o implementare posibilă:
Atenție: stinga este prima poziție in vectorul căutat, iar dreapta este prima poziție în afara vectorului căutat. Dacă respectați această convenție evitați bug-urile de final de căutare cînd indicii rămîn pe loc și o condiție incorectă in while poate să ducă la o buclă infinită.
#include <stdio.h>
int main(){
int n, i, m, val, st, dr, gasit, mij;
scanf( "%d", &val );
st = 0;
dr = n - 1;
gasit = 0;
while( st <= dr && !gasit ) {
mij = ( st + dr ) / 2;
if( val == v[mij] )
gasit = 1;
else if( val < v[mij] )
dr = mij - 1;
else
st = mij + 1;
}
printf( "%d ", gasit );
}
return 0;
}Temă
- Tema 23 de pe pbinfo
- runda_varena
Indicatii: la problema kdiv, vom adapta ciurul lui eratostene astfel incat sa nu tinem in ciur valori de 0 si 1 ci numarul de divizori primi ai fiecarui numar. De pilda, daca vrem sa marcam ce numere au ca divizor prim pe 2, vom marca toate numerele multiplu 2, inclusiv pe 2. Cum vom marca? Adunam 1 la casuta fiecarui numar multiplu de 2, semn ca am gasit un divizor prim.
Pregatire olimpiada
Rezolvati problemele din runda de pe varena:
Ciur
Ciur, Compactare Ciur
Ciur modificat
- http://varena.ro/problema/kdiv aplicație a ciurului lui Eratostene - folosim ciurul pentru a memora pentru fiecare numar cati divizori primi are fiecare numar
- intervale
- 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
- intervale clasa a 7a idem kdiv, +sume partiale
