Bella: /* Formula lui Legendre */

2023-03-14T20:48:48Z

Formula lui Legendre

New page

= Lectie =
==Descompunerea in factori primi ==
[https://www.pbinfo.ro/probleme/62/factorizare factorizare]
Se citeşte un număr natural n. Să se afişeze descompunerea în factori primi a lui n.

'''Pseudocod'''
intreg n, d, p
citeste n
d = 2
while( d * d <= n )
p = 0
while( n % d == 0 )
n = n / d
p = p + 1
if( p > 0 )
scrie d, " ", p
d = d + 1
if ( n > 1 )
scrie n, " ", 1
<syntaxhighlight>
#include <stdio.h>
int main(){
int n, d, p;
scanf("%d",&n); // cin >> n;

d = 2;
while( d * d <= n ){
p = 0; // puterea la care apare d in descompunere
while( n % d == 0 ){ // impartim repetat la d si numaram de cate ori n se imparte la d
n = n / d;
p = p + 1;
}
if( p > 0 ) ]// daca puterea este nenula, atunci d e factor prim
printf( "%d %d\n", d, p ); // tiparim factorul prim si puterea ( in c++ cout << d << " "<< p <<"\n"; )
d = d + 1;
}
if ( n > 1 ) // daca n > 1 atunci in n a mai ramas un factor prim la puterea 1
printf( "%d 1", n ); // cout << n << " " << 1;

return 0;
}
</syntaxhighlight>

== Variante de implementare a descompunerii in factori primi ==
Problema factorizare ne cere afisarea fiecarui factor prim si a puterii pe cate o linie. Este posibil insa ca formatul afisarii sa difere, de pilda, putin mai dificil, este sa afisam descompunerea in factori sub forma unui produs. Ex: Daca n = 12 vom afisa: 2^2 * 3. Putem observa ca in fata fiecarui factor va trebui sa afisam un semn *, mai putin in fata primului factor.

====Varianta1 cu while-do ====
'''Pseudocod'''
intreg n, p, d, pas
citeste n
d = 2
pas = 1
while( n > 1 )
p = 0
while( n mod d == 0 )
n = n div d
p = p + 1
if( p > 0 ) // daca am gasit un factor prim
if( pas == 1 ) // daca e primul factor
scrie d, "^", p // afisam factorul fara steluta in fata
pas = pas + 1; // modificam variabila stegulet
else // daca nu suntem la pasul 1
scrie " * ", d , "^", p // afisam cu *
d = d + 1;

<syntaxhighlight>
#include<stdio.h>
int main(){
int n, p, d, pas;
scanf( "%d", &n ); /// cin >> n;
d = 2; pas = 1;
while( n > 1 ){ /// cata vreme n nu a fost descompus
p = 0; /// impartim pe n la d de cate ori se poate
while( n % d == 0 ){
n= n / d;
p = p + 1; /// rezulta p, ca fiind puterea divizorului
}
if( p > 0 )
if( pas == 1 ){
printf("%d^%d", d, p); /// cout << d << "^" << p;
pas = pas + 1;
}
else
printf("*%d^%d", d, p); /// cout << "*"<< d << "^" << p;
d = d + 1;
}
return 0;
}
</syntaxhighlight>

Putem privi afisarea de mai sus, ca o afisare la care dupa fiecare termen pun o steluta, mai putin dupa ultimul termen. Mai jos este implementarea acestei idei.
=== Varianta 2 ===

<syntaxhighlight>

#include <stdio.h>
int main(){
int n, d, p;
scanf( "%d", &n ); // cin>>n;
d = 2;
while( n != 1 ){
p = 0;
while( n % d == 0 ){
n = n / d;
p = p + 1;
}
if( p != 0 )
if( n == 1 ) // daca n a devenit 1, atunci am gasit un ultim factor
printf( "%d^%d", d, p ); // cout << d < <"^" << p;
else
printf( "%d^%d*", d, p ); // cout << d << "^" << p << "*";
d = d + 1;
}
return 0;
}
</syntaxhighlight>

====Varianta2 cu do-while ====
<syntaxhighlight>
using namespace std;
int main(){
int n, d, p;
scanf( "%d",&n ); // cin >> n;
d = 2;
do{
p = 0;
while( n % d == 0 ){
n = n / d;
p = p + 1;
}
if(p != 0)
if(n == 1) // ca am gasit un ultim factor
printf( "%d^%d", d, p ); // cout << d << "^" <<p;
else
printf( "%d^%d*", d, p ); // cout << d << "^" << p<< "*";
d = d + 1;
}while( n != 1 );
return 0;
}
</syntaxhighlight>

== Divizori primi ==
Sa se afiseze cati divizori primi are un număr n.
Tendinta multora cand e vorba de aceasta problema este de a parcurge toti divizorii numarului si de a-i verifica pe fiecare in parte daca sunt primi. Nu trebuie insa decat sa descompunem in factori, folosind algoritmul precedent si sa numaram factorii primi gasiti.

<syntaxhighlight>
#include <iostream>
#include <stdio.h>
using namespace std;
int main(){
int n, d, p, nrdiv = 0;
scanf( "%d", &n );

d = 2;
while( d * d <= n ){
p = 0;
while( n % d == 0 ){
n = n / d;
p = p + 1;
}
if( p > 0 )
nrdiv = nrdiv + 1;

d = d + 1;
}
if ( n > 1 )
nrdiv = nrdiv + 1;

printf("%d", nrdiv );
return 0;
}
</syntaxhighlight>
Aplicatie: [https://www.pbinfo.ro/probleme/462/divprimmax divprimmax]

== Cel mai mic divizor prim ==
Sa se afiseze cel mai mic divizor prim pe care il are un număr n.
Rezolvare1: Putem folosi algoritmul care determina divizorii unui numar din lectia precedenta, oprindu-ne la primul divizor gasit. Acesta va fi cu siguranta si divizor prim.
Rezolvare2: Ne vom folosi tot de descompunerea in factori primi, descompunere pe care o vom intrerupe cand am gasit primul factor primi. Iata o implementare a acestei idei.
<syntaxhighlight>
#include <iostream>
#include <stdio.h>
using namespace std;
int main(){
int n, d, p, div = 0;
scanf( "%d", &n );
d = 2;
while( d * d <= n && !div ){
p = 0;
while( n % d == 0 ){
n = n / d;
p = p + 1;
}
if( p > 0 )
div = d;

d = d + 1;
}
if ( n > 1 )
div = n;
printf("%d", div );

return 0;
}
</syntaxhighlight>
Aplicatie: [https://www.pbinfo.ro/probleme/443/divizoriprimi divizoriprimi]

== Cel mai mare divizor prim ==
Sa se afiseze cel mai mare divizor prim a unui număr n?
<syntaxhighlight>
#include <iostream>
#include <stdio.h>
using namespace std;
int main(){
int n, d, p;
scanf( "%d", &n );
int dmax;
d = 2;
while( d * d <= n ){
p = 0;
while( n % d == 0 ){
n = n / d;
p = p + 1;
}
if( p > 0 )
dmax = d;
d ++;
}
if ( n > 1 )
dmax = n;
printf("%d", dmax );

return 0;
}
</syntaxhighlight>
Aplicatie: [https://www.pbinfo.ro/probleme/1409/numere11 numere11]

= Formule de calcul =
== Formula lui Legendre ==
Cu ajutorul acesteia determinam exponentul unui numar prim k in descompunerea in factori primi a lui n factorial. N factorial se noteaza cu n! si e produsul primelor n numere naturale.

n! = 1 *2 * 3 * 4 * 5...* n

Putem observa ca in sirul celor n numere vom avea din k in k cate un numar divizibil cu k, printre acestea sunt si numere divizibile cu k^2 (k la puterea a doua ), pentru care mai trebuie sa numaram cate un k pentru fiecare.
Cate numere sunt divizibile cu k pana la n? R: n/k
Dar cate numere sunt divizibile cu k * k pana la n ? k^2 / n
Cati de k vom avea in aceste numere? k + k^2 / n (caten umere divizibile cu k si cate numere divizibile cu k^2)
Extindem aceasta idee gandindu-ne ca pana la n mai putem avea si numere divizibile cu k^3, k^4, astfel va trebui sa numaram si pentru acestea cate un k. Rezulta formula:

exp = n/k + n/k^2 +.... + n/k^p, unde k^p <= n, altfel fractia ar deveni 0

Aplicatie:[https://www.varena.ro/problema/exponent exponent]Se dă un număr natural n şi o cifră k din mulţimea {2, 3, 5, 7}. Se cere să se afişeze exponentul lui k în descompunerea în factori primi a produsului 1·2·3·...·n.
<syntaxhighlight>
#include <fstream>

using namespace std;
ifstream fin ("exponent.in");
ofstream fout ("exponent.out");
int main(){
int n, k, p, s;
fin >> n >> k;
p = k;
s = 0;
while ( n / p ){
s += n / p;
p *= k;
}
fout << s;
return 0;
}</syntaxhighlight>

== Numarul de divizori ai unui numar ==
Fie <math>n = d_1^{p_1} * d_2^{p_2}*\cdots *d_k^{p_k}</math> este descompunerea în factori primi a lui n.

<math >Nrdiv = (p_{1}+1)*(p_{2}+1)*...*(p_{k}+1) </math>

== Suma divizorilor unui numar ==
<math>S = \dfrac{d_{1}^{p_{1}+1}-1}{d_{1}-1}*\dfrac{d_{2}^{p_{2}+1}-1}{d_{2}-1}*...*\dfrac{d_{k}^{p_{k}+1}-1}{d_{k}-1}</math>

Aplicati formula in problema: [https://www.pbinfo.ro/?pagina=probleme&id=1574 Prietene]
Tema:[https://infoarena.ro/problema/sumdiv sumdiv]

== Numarul de numere prime cu n mai mici ca n (Indicatorul lui Euler) ==
* [https://www.pbinfo.ro/?pagina=probleme&id=1908 Fractii_ired]
Problema cere de fapt, cate numere din intervalul [1,n] sunt prime cu n. O prima solutie este sa calculam cmmdc dintre n si fiecare numar x din intervalul [1,n]. Daca cmmdc(x, n) este 1, atunci x/n e fractie ireductibila. Aceasta solutie insa este lenta, parcurgerea tuturor valorilor de la 1 la n consuma f. mult timp.
O alta solutie este data de [https://ro.wikipedia.org/wiki/Indicatorul_lui_Euler Indicatorul lui Euler]
Indicatorul lui Euler se determina folosind tot descompunerea in factori primi, calculand formula:

<math>\phi(n)= (p_{1}-1)p_{1}^{k_{1}-1} * (p_{2}-1)p_{2}^{k_{2}-1}* \cdots *(p_{r}-1)p_{r}^{k_{r}-1}</math>

Formula se poate reduce astfel incat algoritmul sa poata fi mai usor implementat :

<math>\phi(n)=n * \dfrac{(p_{1}-1)}{p_{1}} * \dfrac{(p_{2}-1)}{p_{2}}* \cdots * \dfrac{(p_{r}-1)}{p_{r}}</math>

== Tema ==
Filtrare probleme cu descompunerea in factori primi: [https://www.pbinfo.ro/?pagina=probleme-lista&disciplina=0&clasa=9&tag=1&subtag=18&dificultate=0&folosesc_consola=-1&eticheta=55,&start=0 Probleme Pbinfo]
===Teorie ===
Descompunerea in factori primi:
* [https://www.pbinfo.ro/?pagina=probleme&id=62 Factorizare] in curs
* [https://www.pbinfo.ro/probleme/1319/descompunere-factori descompunere-factori] teorie

=== Tema Laborator ===
'''Descompunerea in factori primi''':
* [https://www.pbinfo.ro/?pagina=probleme&id=63 Factorizare1]
* [https://www.pbinfo.ro/probleme/435/factoriprimi Factoriprimi]
* [https://www.pbinfo.ro/?pagina=probleme&id=268 Divk]
* [https://www.pbinfo.ro/?pagina=probleme&id=1319 Descompunere_factori]
* [https://www.pbinfo.ro/probleme/389/divizoripariinterval divizoripariinterval]
(dificile)
* [https://www.pbinfo.ro/probleme/664/nrperechi nrperechi] produs cartezian de perechi
Alte:
* https://www.varena.ro/problema/exponent

'''Codeforces'''
* [https://codeforces.com/contest/797/problem/A A - k-Factorization] descompunere in factor primi

Clasa a IX-a lecția 8 - Revision history

Bella: /* Formula lui Legendre */