Bella: /* Ciurul lui Eratostene */

2018-09-20T13:30:43Z

Ciurul lui Eratostene

New page

= Lectie =

== Descompunerea in factori primi ==
O implementare a acestei probleme de complexitate O(sqrt(n)):
<syntaxhighlight>
#include <stdio.h>

int main() {
int n, div, exp;

scanf("%d", &n);
div = 2; //Incepem cautarea factorilor primi de la primul numar prim
while ( div * div <= n ) { //Cautam factorii primi pana la radicalul lui n
exp = 0;
while ( n % div == 0 ) {
n /= div;
exp++;
}
if (exp > 0)
printf("%d^%d\n", div, exp);
div++;
}
// daca n mai contine un factor, el este un numar prim la puterea unu
if ( n > 1 )
printf( "%d^1\n", n );

return 0;
}</syntaxhighlight>

== Numarul de divizori si suma divizorilor ==

Fie descompunerea unui numar n in factori primi:

<math>
n= d_1^{p_1} \ast d_2^{p_2} \ast ... \ast d_k^{p_k}
</math>

===Numarul de divizori va fi===

<math>\mathit{nrdiv}=\left({p}_{1}+1\right)\ast \left({p}_{2}+1\right)\ast \mathrm{...}\ast \left({p}_{k}+1\right)</math>

===Suma divizorilor===

<math>\mathit{sdiv}=\frac{{d}_{1}^{p1+1}-1}{{d}_{1}-1}\ast \frac{{d}_{2}^{p2+1}-1}{d2-1}\ast \mathrm{...}\ast \frac{{d}_{k}^{\mathit{pk}+1}-1}{{d}_{k}-1}</math>
== Indicatorul lui Euler ==
[https://ro.wikipedia.org/wiki/Indicatorul_lui_Euler Indicatorul lui Euler] calculeaza numarul de numere din intervalul [1, n], prime cu n.
* [https://www.pbinfo.ro/?pagina=probleme&id=1908 Fractii_ired pbinfo, clasa a 9-a]

== Ciurul lui Eratostene ==
Reamintim aici doar algoritmul studiat anul trecut:

<syntaxhighlight>char ciur[2000000];
...
fscanf( fin, "%d", &n );
ciur[0] = ciur[1] = 1;
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>

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)''.

== Calculul multiplicității unui număr prim în ''n''<nowiki>!</nowiki> ==
Matematicianul [http://en.wikipedia.org/wiki/Adrien-Marie_Legendre Adrien-Marie_Legendre] a descoperit că multiplicitatea (exponentul) unui număr prim ''p'' care apare în descompunerea în factori primi a lui ''n''<nowiki>!</nowiki> poate fi exprimată exact ca:

:<math>Exp(p,n!) = \left \lfloor \frac{n}{p} \right \rfloor + \left \lfloor \frac{n}{p^2} \right \rfloor + \left \lfloor \frac{n}{p^3} \right \rfloor + \cdots = \sum_{i=1}^{\infty} \left \lfloor \frac{n}{p^i} \right \rfloor .</math>

Acest fapt se bazează pe numărarea factorilor ''p'' ai întregilor de la 1 la ''n''. Numărul multiplilor lui ''p'' în numerele de la 1 la ''n'' este <math>\textstyle \left \lfloor \frac{n}{p} \right \rfloor</math>; dar această formulă numără numerele cu doi factori ''p'' o singură dată. De aceea trebuie să mai numărăm încă <math>\textstyle \left \lfloor \frac{n}{p^2} \right \rfloor</math> factori ai lui ''p''. În mod similar pentru trei, patru, cinci factori, pînă la infinit. Însă suma este finită deoarece ''p'' ''i'' este mai mic sau egal cu ''n'' într-un număr finit de valori ale lui ''i'', drept care funcția parte întreagă va fi zero pentru toate celelalte valori.

Cînd scriem programul pentru calculul exponentului ne vom opri la acel ''i'' pentru care ''pi > n''.

== Calculul multiplicității unui număr prim la o putere în ''n''<nowiki>!</nowiki> ==
Este simplu de demonstrat că dacă avem un număr prim ''p'' la o putere ''k'' atunci multiplicitatea lui ''pk'' în ''n''<nowiki>!</nowiki> este

:<math>Exp(p^k,n!) = \frac{Exp(p,n!)}{k}</math>

== Calculul multiplicității unui număr oarecare în ''n''<nowiki>!</nowiki> ==
Este simplu să arătăm că dacă avem un număr ''a'' a cărui descompunere în factori primi este

:''a = p1k1 • p2k2 • … • pmkm''

atunci multiplicitatea (exponentul) lui ''a'' în ''n''<nowiki>!</nowiki> este

:<math>Exp(a,n!) = min(Exp(p_1^{k_1},n!),Exp(p_2^{k_2},n!),\ldots,Exp(p_m^{k_m},n!))</math>

sau

:<math>Exp(a,n!) = min(\frac{Exp(p_1,n!)}{k_1},\frac{Exp(p_2,n!)}{k_2},\ldots,\frac{Exp(p_m,n!)}{k_m})</math>

== TEMA ==

* [http://varena.ro/problema/factk factk] .campion 2004 [http://isa.algopedia.ro/wiki/index.php/factk Rez]
* [http://varena.ro/problema/fact fact] ONI 2006 clasa a 9-a [http://isa.algopedia.ro/wiki/index.php/fact Rez]
* [http://varena.ro/problema/treidiv trei divizori][http://isa.algopedia.ro/wiki/index.php/treidiv Rez]

=== Ciur ===
* [http://varena.ro/problema/prime prime], Ioana Bica [http://isa.algopedia.ro/wiki/index.php/prime Rez]

* [http://varena.ro/problema/bileprime bileprime] campion 2010, (inca nu e pusa) [http://isa.algopedia.ro/wiki/index.php/bileprime Rez]

* [http://varena.ro/problema/paisprezece paisprezece] [http://isa.algopedia.ro/wiki/index.php/paisprezece Rez]

=== Ciur, Compactare Ciur ===
* [http://varena.ro/problema/prime1 prime1], campion2005 (inca nu e pusa)
http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=365
* [http://varena.ro/problema/sprime sprime], XOR 2015 clasa a 9 a

=== Ciur, (Compactare ciur), Legendre ===

* [http://varena.ro/problema/factori Factori], OJI 2012 (clasa a 6-a) [http://isa.algopedia.ro/wiki/index.php/Factori Rezolvare]

Clasa a VI-a lecția 4 - Revision history

Bella: /* Ciurul lui Eratostene */