Cerc 6 2018 lectia 2

Lectie

Descompunerea in factori primi

O implementare a acestei probleme de complexitate O(sqrt(n)):

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

Numarul de divizori si suma divizorilor

Fie descompunerea unui numar n in factori primi:

$n=d_{1}^{p_{1}}\ast d_{2}^{p_{2}}\ast ...\ast d_{k}^{p_{k}}$

Numarul de divizori va fi:

${\mathit {nrdiv}}=\left({p}_{1}+1\right)\ast \left({p}_{2}+1\right)\ast \mathrm {...} \ast \left({p}_{k}+1\right)$

Suma divizorilor:

${\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}}$

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:

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;

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

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

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

Calcului sumei divizorilor

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;

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

TEMA

Descompunere in factori primi si nr divizoril

• nepatratRez
• divmulRez

Ciur

• paisprezece Rez
• primRez