Am facut cu doua variante, dar pentru amandoua se trece de limita de timp.
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("eratostene7.in");
ofstream fout("eratostene7.out");
int n, i, k, x, v[1000000], nr[1000000], j;
int main()
{
fin >> n;
int p[1000000];
for (i = 1; i <= 1000000; i++) p[i] = 1;
v[1] = v[0] = 1;
for (i = 2; i * i <= 1000000; i++)
if (v[i] == 0) {
p[i] = i;
nr[i]=1;
for (j = 2 * i; j <= 1000000; j = j + i) {
v[j] = 1; p[j] = p[j] * i; nr[j] = nr[j] + 1;
}
}
for (i = 1; i <= n; i++) {
fin >> x >> k;
if (x == p[x] && nr[x] == k) fout << "DA" << endl;
else fout << "NU" << endl;
}
return 0;
}
A doua varianta
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("eratostene7.in");
ofstream fout("eratostene7.out");
int n, i, k, k2, x, d, ok;
int main()
{
fin >> n;
for (i = 1; i <= n; i++) {
fin >> x >> k;
k2 = 0;
d = 2;
ok = 0;
while (x > 1) {
if (x%d == 0) {x = x/d; ok ++; k2++;}
else {ok = 0; d++;}
if (ok > 1 || k2 > k) {ok = 0; x = 1;}
}
if (ok == 1 && k2 == k) fout << "DA" << endl;
else fout << "NU" << endl;
}
return 0;
}
