# PBinfo #2332 – primXXL – Rezolvare C++

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

## Enunț

Cerința
Se dau n numere naturale şi un număr natural k. Aflaţi câte dintre numerele date îl divid pe k! ( k factorial).

Date de intrare
Fișierul de intrare primxxl.in conține pe prima linie numerele n şi k, iar pe a doua linie n numere naturale nenule separate prin spații.

Date de ieșire
Fișierul de ieșire primxxl.out va conține pe prima linie numărul d, reprezentând numărul numerelor de pe a doua linie a fișierului de intrare care îl divid pe k!.

Restricții și precizări

1 ≤ n ≤ 10.000
1 ≤ k ≤ 1.000.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000

Exemplu:
primxxl.in

3 5
20 3 14
primxxl.out

2
Explicație
Avem k!=5!=120, iar dintre numerele date 20 şi 3 îl divid pe 120, deci două numere.

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
ifstream f("primxxl.in");
ofstream g("primxxl.out");
long long n,k,i,j,m,x,prod,nr,ok,ep,v[32002],p[3500],e[3500] ;
int main()
{
    f >> n >> k ;
    // numerele prime pana la 32000 si exponentii lor in k!
    v[2]=0 ;
    for(i=2 ; i<=32000 ; i++)
        if(v[i]==0)
    {
        m++ ;
        p[m] = i ;
        e[m] = 0 ;
        prod = i ;
        while ( prod<=k )
        {
            e[m] += k/prod ;
            prod = prod*i ;
        }
        j = i+i ;
        while ( j<=32000 )
        {
            v[j] = 1 ;
            j = j+i ;
        }
    }
    nr = 0 ;
    for ( i=1 ; i<=n ; i++ )
    {
        f >> x ;
        if( x<=k ) nr++ ;
        else
        {
        j = 1 ;
        ok = 1 ;
        while (( p[j]*p[j]<=x )and(ok==1))
        {
            ep = 0 ;
            while( x%p[j]==0 )
            {
                ep++ ;
                x = x/p[j] ;
            }
            if( ep>e[j] ) ok=0 ;
            j++ ;
        }
        if ( x>k ) ok=0 ;
        if( ok==1 ) nr++ ;
        }
    }
    g << nr ;
    return 0;
}
```

## Resurse

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