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

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!)=\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 .

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 $\textstyle \left\lfloor {\frac {n}{p}}\right\rfloor$ ; dar această formulă numără numerele cu doi factori p o singură dată. De aceea trebuie să mai numărăm încă $\textstyle \left\lfloor {\frac {n}{p^{2}}}\right\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!),\ldots ,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}}},\ldots ,{\frac {Exp(p_{m},n!)}{k_{m}}})

TEMA

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

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

Clasa a VI-a lecția 4

Contents