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;
}
