# PBinfo #1474 – exponent – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Softescu a învăţat azi la şcoală, la ora de informatică algoritmul determinării exponentului unui număr natural prim p în descompunerea în factori primi a lui n!.
Softescu s-a gândit  că ar fi interesant dacă ar putea să elaboreze un algoritm care să determine exponentul unui număr natural oarecare, a (a>1) în descompunerea în factori primi a lui n!.

Cerința
Dându-se două numere naturale n şi a, nenule, se cere să se determine exponentul numărului natural a  în descompunerea lui n!.

Date de intrare
Fişierul de intrare exponent.in conţine pe prima linie două numere naturale, nenule, n a separate printr-un spațiu.

Date de ieșire
Fişierul de ieşire exponent.out va conţine pe prima linie un număr natural e, reprezentând exponentul numărului natural a în descompunerea în factori primi a lui n! .

Restricții și precizări

2 ≤ n,a ≤ 1000
pentru 30% dintre teste, 2 ≤ n,a ≤ 200
exponentul unui număr natural nenul x, nu neapărat prim, în descompunerea unui număr natural nenul y este cel mai mare număr natural e cu proprietatea că xe este divizor al lui y.

Exemplu:
exponent.in

6 4
exponent.out

2
Explicație
6!=1*2*3*4*5*6 = 1*32*42*5.

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
ifstream fin("exponent.in");
ofstream fout("exponent.out");
int n,a,k,m,ciur[1001],c[1001],p[1001],e[1001],ea[1001],emin;
void ciurul()
{
    int i,j;
    ciur[0]=ciur[1]=1;
    for(i=2;i<=1000;i++)
    {
        if(ciur[i]==0)
           {k++;
            c[k]=i;
            for(j=i*i;j<=a;j=j+i)
                ciur[j]=1;
           }
    }
}
int exp(int p)
{
    int ex=0,f=p;
    do{
        ex=ex+n/f;
        f=f*p;
      }while(n/f!=0);
    return ex;
}
int main()
{int i,ex;
    fin>>n>>a;
    ciurul();
    i=1;
    while(a>1&&i<=k)
    {
        ex=0;
        while(a%c[i]==0)
        {
            ex++;
            a=a/c[i];
        }
        if(ex)
        {
            m++;
            p[m]=c[i];
            ea[m]=ex;
        }
        i++;
    }
    for(i=1;i<=m;i++)
        {
          e[i]=exp(p[i]);
        }
    emin=e[1]/ea[1];
    for(i=2;i<=m;i++)
        if(e[i]/ea[i]<emin)
             emin=e[i]/ea[i];
    fout<<emin<<'\n';
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1474)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1474/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1474/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)