Lectie

Descompunerea in factori primi

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

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

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;

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

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

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

Varianta2 cu do-while

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

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.

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

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

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

Aplicatie: divizoriprimi

Cel mai mare divizor prim

Sa se afiseze cel mai mare divizor prim a unui număr n?

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

Aplicatie: 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:exponentSe 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.

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

Numarul de divizori ai unui numar

Fie $n=d_{1}^{p_{1}}*d_{2}^{p_{2}}*\cdots *d_{k}^{p_{k}}$ este descompunerea în factori primi a lui n.

$Nrdiv=(p_{1}+1)*(p_{2}+1)*...*(p_{k}+1)$

Suma divizorilor unui numar

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

Aplicati formula in problema: Prietene Tema:sumdiv

Numarul de numere prime cu n mai mici ca n (Indicatorul lui Euler)

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 Indicatorul lui Euler Indicatorul lui Euler se determina folosind tot descompunerea in factori primi, calculand formula:

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

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

$\phi (n)=n*{\dfrac {(p_{1}-1)}{p_{1}}}*{\dfrac {(p_{2}-1)}{p_{2}}}*\cdots *{\dfrac {(p_{r}-1)}{p_{r}}}$

Tema

Filtrare probleme cu descompunerea in factori primi: Probleme Pbinfo

Teorie

Descompunerea in factori primi:

Factorizare in curs
descompunere-factori teorie

Tema Laborator

Descompunerea in factori primi:

(dificile)

nrperechi produs cartezian de perechi

Alte:

https://www.varena.ro/problema/exponent

Codeforces

A - k-Factorization descompunere in factor primi

Clasa a IX-a lecția 8

Contents