Clasa a VI-a lecția 4

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

${n}{r}{d}{i}{v}=(p_1+1)\ast (p_2+1)\ast \mathrm{.}\mathrm{.}\mathrm{.}\ast (p_k+1)$

Suma divizorilor

${s}{d}{i}{v}=\frac{d_1^{p1+1}-1}{d_1-1}\ast \frac{d_2^{p2+1}-1}{d2-1}\ast \mathrm{.}\mathrm{.}\mathrm{.}\ast \frac{d_k^{{p}{k}+1}-1}{d_k-1}$

Indicatorul lui Euler

Indicatorul lui Euler calculeaza numarul de numere din intervalul [1, n], prime cu n.

• Fractii_ired pbinfo, clasa a 9-a

Ciurul lui Eratostene

Reamintim aici doar algoritmul studiat anul trecut:

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;

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

Calculul multiplicității unui număr prim în n!

Matematicianul Adrien-Marie_Legendre a descoperit că multiplicitatea (exponentul) unui număr prim p care apare în descompunerea în factori primi a lui n! poate fi exprimată exact ca:

$Exp(p,n!)=\lfloor \frac{n}{p}\rfloor +\lfloor \frac{n}{p^2}\rfloor +\lfloor \frac{n}{p^3}\rfloor +\cdots =\sum _{i=1}^{\mathrm{\infty }}\lfloor \frac{n}{p^i}\rfloor .$

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 $\lfloor \frac{n}{p}\rfloor$; dar această formulă numără numerele cu doi factori p o singură dată. De aceea trebuie să mai numărăm încă $\lfloor \frac{n}{p^2}\rfloor$ factori ai lui p. În mod similar pentru trei, patru, cinci factori, pînă la infinit. Însă suma este finită deoarece p ⁱ 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 pⁱ > n.

Calculul multiplicității unui număr prim la o putere în n!

Este simplu de demonstrat că dacă avem un număr prim p la o putere k atunci multiplicitatea lui p^k în n! este

$Exp(p^k,n!)=\frac{Exp(p,n!)}{k}$

Calculul multiplicității unui număr oarecare în n!

Este simplu să arătăm că dacă avem un număr a a cărui descompunere în factori primi este

a = p₁^k₁ • p₂^k₂ • … • p_m^k_m

atunci multiplicitatea (exponentul) lui a în n! este

$Exp(a,n!)=min(Exp(p_1^{k_1},n!),Exp(p_2^{k_2},n!),\dots ,Exp(p_m^{k_m},n!))$

sau

$Exp(a,n!)=min(\frac{Exp(p_1,n!)}{k_1},\frac{Exp(p_2,n!)}{k_2},\dots ,\frac{Exp(p_m,n!)}{k_m})$

TEMA

• factk .campion 2004 Rez
• fact ONI 2006 clasa a 9-a Rez
• trei divizoriRez

Ciur

• prime, Ioana Bica Rez

• bileprime campion 2010, (inca nu e pusa) Rez

• paisprezece Rez

Ciur, Compactare Ciur

• prime1, campion2005 (inca nu e pusa)

http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=365

• sprime, XOR 2015 clasa a 9 a

Ciur, (Compactare ciur), Legendre

• Factori, OJI 2012 (clasa a 6-a) Rezolvare