Bella: /* Utilizarea Ciurului lui Eratostene */

2020-12-04T07:26:37Z

Utilizarea Ciurului lui Eratostene

New page

== 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:

# <nowiki>Creează o listă a întregilor consecutivi de la 2 la n: [2, 3, 4, ..., n].</nowiki>
# 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ță, <tt>ciur</tt>, care pentru fiecare număr între <tt>2</tt> și <tt>n</tt> ne va spune dacă este tăiat sau nu. Inițial vectorul <tt>ciur</tt> 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 <tt><nowiki>ciur[x]</nowiki></tt> va fi zero dacă numărul este prim, sau unu în caz contrar. Deoarece elementele lui <tt>ciur</tt> 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 <tt>n</tt>, cu <tt>n</tt> maxim două milioane:

<syntaxhighlight>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;</syntaxhighlight>

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

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

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

<syntaxhighlight>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;</syntaxhighlight>
= 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...
<syntaxhighlight>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;
</syntaxhighlight>

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

<syntaxhighlight>
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;
</syntaxhighlight>

Nu uitați:
* Vectorul <tt>ciur[]</tt> este de tip caracter și nu întreg!
* În final vectorul <tt>ciur[i]</tt> este <tt>0</tt> dacă numărul este prim sau <tt>1</tt> î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:

<syntaxhighlight>
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]++;
</syntaxhighlight>

De asemenea putem calcula similar suma divizorilor pentru numerele de la 1 la n:
<syntaxhighlight>
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;
</syntaxhighlight>

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

<syntaxhighlight>
#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;
...................
}
</syntaxhighlight>

<syntaxhighlight>
#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;
}
</syntaxhighlight>

https://infoarena.ro/problema/divprim

= Temă =
== Tema Teorie ==
Tema 23 de pe pbinfo

== Tema Laborator ==
Rezolvati problemele din runda de pe varena:
* [http://varena.ro/runda/c2_9 Tema 24]
** [http://varena.ro/problema/apropiate apropiate]
** [http://varena.ro/problema/apropiate1 apropiate1]
** [http://varena.ro/problema/extraprime extraprime]
** [http://varena.ro/problema/prime prime]
** [http://varena.ro/problema/kdiv kdiv]

=== Ciur ===
* [http://varena.ro/problema/prime prime], Ioana Bica [http://isa.algopedia.ro/wiki/index.php/prime Rez]
* [http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=1176 bileprime] campion 2010, (inca nu e pusa pe varena) [http://isa.algopedia.ro/wiki/index.php/bileprime Rez]
* [http://varena.ro/problema/paisprezece paisprezece] [http://isa.algopedia.ro/wiki/index.php/paisprezece Rez]
* [https://www.pbinfo.ro/?pagina=detalii-evaluare&id=7712114 extraprime]
=== Ciur, Compactare Ciur ===
* [http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=365 prime], campion2005 (inca nu e pusa pe varena)
* [http://varena.ro/problema/sprime sprime], XOR 2015 clasa a 9 a

=== Ciur modificat ===
* [http://varena.ro/problema/kdiv kdiv] aplicație a ciurului lui Eratostene - folosim ciurul pentru a memora pentru fiecare numar cati divizori primi are fiecare numar
* [http://varena.ro/problema/intervale 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
* [http://varena.ro/problema/prim prim] dată la ONI 2003 clasa a 5<sup>a</sup>
* [http://varena.ro/problema/cub1 cub1] dată la ONI 2002 clasa a 5<sup>a</sup>

Clasa a IX-a lecția 25 - Revision history

Bella: /* Utilizarea Ciurului lui Eratostene */