# PBinfo #2328 – prim013 – Rezolvare C++

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

## Enunț

Dorel este pasionat de feng shui. Astfel, pentru a-şi crea un cadru adecvat  meditaţiei, s-a hotărât să scrie pe pereţii casei numere care au un număr prim de divizori. El a găsit n numere, însă nu ştie să le aleagă pe cele potrivite.  

Cerința
Se dau n numere naturale. Aflaţi câte dintre acestea au un număr prim de divizori.

Date de intrare
Fișierul de intrare prim013.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale nenule separate prin spații.

Date de ieșire
Fișierul de ieșire prim013.out va conține pe prima linie numărul de numere care au un număr prim de divizori.

Restricții și precizări

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

Exemplu:
prim013.in

5
1 3 6 9 625
prim013.out

3
Explicație
Numerele 3,9,625 au 2,3 respectiv 5 divizori, numărul divizorilor fiind prim. În total sunt 3 numere cu numărul divizorilor prim.

## Cod sursă C++

```cpp
#include <fstream>
#define m 10000000
using namespace std;
ifstream f("prim013.in");
ofstream g("prim013.out");
long long n,i,j,e,nr,x,p[30];
char v[m+1] ;
int main()
{
    p[1] = 1 ;
    p[2] = 0 ;
    for( i=2 ; i<=25 ; i++ )
        if ( p[i]==0)
        {
            j = i+i ;
            while ( j<=25 )
            {
                p[j] = 1 ;
                j = j+i ;
            }
        }
    //ciurul lui Eratostene
    v[1] = 1 ;
    v[2] = 0 ;
    for ( i=2 ; i<=m ; i++ )
        if( v[i]==0 )
        {
            j = i+i ;
            while ( j<=m )
            {
                v[j] = 1 ;
                j = j+i ;
            }
            //bifez puterile lui i-prim care au exponentul=nr.prim-1 , cu 2
            if ( i<=3162 )
            {
               j = i*i ;
               e = 2 ;
               while( j<=m )
               {
                   if ( p[e+1]==0 ) v[j] = 2 ;
                   j = j*i ;
                   e++ ;
               }
            }
        }
    nr = 0 ;
    f >> n ;
    for ( i=1 ; i<=n ; i++ )
    {
        f >> x ;
        if ( v[x]!=1 ) nr++ ;
    }
    g << nr ;
    return 0;
}
```

## Resurse

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