View source for Cerc 6 2018 lectia 2

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

Vezi demonstratia matematica a formulelor in caiet

=== Studiu de caz Problema divmul - infoarena ===
In caiete

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

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

===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, &*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 c7 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>

== 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>
===Calcului sumei divizorilor ===
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>

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&nbsp;log&nbsp;n)''.

== TEMA ==
=== Descompunere in factori primi si nr divizoril ===
* [http://varena.ro/problema/nenepatrat nepatrat][http://isa.algopedia.ro/wiki/index.php/nenepatrat Rez]
* [https://www.infoarena.ro/problema/divmul divmul][http://isa.algopedia.ro/wiki/index.php/divmul Rez]

=== Ciur ===
* [http://varena.ro/problema/paisprezece paisprezece] [http://isa.algopedia.ro/wiki/index.php/paisprezece Rez]
* [https://infoarena.ro/problema/prim prim][http://isa.algopedia.ro/wiki/index.php/prim Rez]