Răspuns:
#include <fstream>
#include <bitset>
#define N 1000000
using namespace std;
struct PRIME
{
int pr,exp;
};
PRIME prime[N];
bitset <N>a;
int pl;
int GasescPutereP(int K,int p)
{
int exp=0;
while(K)
K/=p,exp+=K;
return exp;
}
void Ciur(int K)
{
a[1]=1;
for(int d=2;d<=K;++d)
if(a[d]==0)
{
prime[++pl].pr=d;
prime[pl].exp=GasescPutereP(K,d);
int j=d+d;
while(j<=K)
a[j]=1,j+=d;
}
}
bool primeFactorsofK(int numar,int k)
{
int counta=0;
while(!(numar%2))
numar>>=1,++counta;
if(counta>prime[1].exp)
return false;
if(numar>1)
for(int i=2;i<=pl&&numar>1;++i)
{
if(numar%prime[i].pr==0)
{
counta=0;
while(numar%prime[i].pr==0)
numar=numar/prime[i].pr,++counta;
if(counta>prime[i].exp)
return false;
}
if(prime[i].pr*prime[i].pr>numar)
break;
}
if(numar==1)
return true;
else
if(numar<=k)
return true;
else
return false;
}
int main()
{
ifstream f("primxxl.in");
int n,k;
f>>n>>k;
Ciur(k);
int x,nr=0;
while(n--)
{
f>>x;
if(primeFactorsofK(x,k))
++nr;
}
f.close();
ofstream g("primxxl.out");
g<<nr;
g.close();
return 0;
}
Explicație:
