Question

#1931 Fantastice

Cerința
Definim un număr ca fiind fantastic dacă numărul de numere la care acesta se împarte exact este un număr prim.

Dându-se un șir cu n numere întregi strict pozitive, să se afișeze numărul de numere fantastice din șir.

Date de intrare
Fișierul de intrare fantastice.in conține pe prima linie numărul n de numere, iar pe cea de-a doua linie, separate prin câte un spaţiu, cele n numere.

Date de ieșire
Fișierul de ieșire fantastice.out va conține pe prima linie numărul de numere fantastice din șir.

Restricții și precizări
1 ≤ n ≤ 106
numerele de pe a doua linie a fișierului de intrare vor fi mai mici sau egale cu 106



Exemplu
fantastice.in

6
21 19 25 16 27 729
fantastice.out

4
Explicație
21 are divizorii 1, 3, 7, 21
19 are divizorii 1, 19
25 are divizorii 1, 5, 25
16 are divizorii 1, 2, 4, 8, 16
27 are divizorii 1, 3, 9, 27
729 are divizorii 1, 3, 9, 27, 81, 243, 729

Deci sunt 4 numere fantastice: 19 25 16 729

acesta este codul meu de 60%
am depasite timp la toate celelalte teste

#include
using namespace std;
ifstream in("fantastice.in");
ofstream out("fantastice.out");
bool prim(int n)
{
int i;
if(n==1)
return 0;
if(n<4)
return 1;
if(n%2==0 || n%3==0)
return 0;
i=5;
while(i*i<=n){
if(n%i==0 || n%(i+2)==0)
return 0;
i+=5;}
return 1;}
int nrdiv(int n)
{int i,c=0;
//c este nr de divizori
for(i=1; i<=n; i++)
{if(n%i==0)c++;}
return c;}
int main()
{int d,x,n,fan=0;
in>>n;
for(int i=1; i<=n; i++){
in>>x;
d=nrdiv(x);
if(prim(d))
fan++;}
out<

Answer 1

#include <fstream>

using namespace std;

ifstream in("fantastice.in");

ofstream out("fantastice.out");

bool prim(int n)

{

   int i;

   if(n==1)

      return 0;

   if(n<4)

      return 1;

   i=2;

   while(i*i<=n){

               if(n%i==0 )

                   return 0;

                   i+=1;

               }

   return 1;

}

int nrdiv(int n)

{int i,c=1,y=2,p;

//c este nr de divizori

while(n>1)

{   p=0;

   while(n%y==0)

   {

       n/=y;p++;

   }

   c=c*(p+1);

   y=y+1;

   if(y*y>n)y=n;

}

return c;

}

int main()

{int d,x,n,fan=0;

in>>n;

for(int i=1; i<=n; i++){

   in>>x;

   d=nrdiv(x);

   if(prim(d))

   fan++;

   }

out<<fan;

}