思路

不妨设 $a \le b$。记使 $a = b$ 的最多操作次数为 $n$，最少操作次数为 $m$。将 $a,b$ 的约数全部除干净，并且每次只除以它们大于一的最小约数时，次数可以取得最大值，为它们质因子次数之和。考虑最少次数 $m$：

1. 若 $a = b$，则 $m = 0$。
2. 若 $a \ne b \wedge a \mid b$，则 $m = 1$。
3. 若 $a \ne b \wedge a \not \mid b$，则 $2 \le a < b$，$m = 2$。第一次 $a/a = 1$，第二次 $b/b = 1$。

当且仅当以下条件同时成立时，问题有解。

1. $m \le k \le n$。
2. $(k = 1 \wedge m = 1) \vee k \ne 1$

证明：若 $n \ge 2$，则 $k$ 可取遍 $[2, n]$ 之间的所有整数。

1. 若 $n = 2$，结论成立。
2. 若 $n > 2$，则 $a$ 的质因子次数之和或者 $b$ 的质因子次数之和其中之一必然大于等于 $2$，不妨设 $b$ 质因子次数之和大于等于 $2$。此时，将 $n$ 次操作中，$b$ 除以它的质因子的其中两次操作 $b / p_1, b / p_2$，其中 $p_1, p_2$ 可能相等，合并为一次 $b / p_1p_2$，则总操作次数减一，变为 $n - 1$ 次，因此 $k$ 可取 $n$ 和 $n - 1$。若 $n - 2 = 1$，结论成立。若 $n - 2 \ge 2$，则对 $(a, b / p_1p_2)$ 递归操作，$k$ 可以取遍 $[2, n - 2]$ 内的所有整数。

时间复杂度 $O(\sqrt {max(a, b)})$。

#include <iostream>

using namespace std;

int div(int n) {
  int se = 0;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0)
      while (n % i == 0) {
        n /= i;
        se++;
      }

  if (n > 1)
    se++;
  return se;
}

void solve() {
  int a, b, k;
  cin >> a >> b >> k;

  if (a > b)
    swap(a, b);

  string ans = "NO";
  if ( (k == 0 && a == b)
    || (k == 1 && a != b && b % a == 0)
    || (k >= 2 && div(a) + div(b) >= k))
    ans = "YES";

  cout << ans << endl;
}

int main() {
  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}