T == N
Tが素数で、Nがその素数で割れる。
TとNが同じ素数の累乗で、Tが2乗以下
以上の３パターンしか Yes の場合はないはず。
bool is_prime(int n)
{
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) return false;
}
return true;
}
class CompositeSmash {
public:
string thePossible(int N, int T)
{
if (T > N) return "No";
if (N == T) return "Yes";
if (N % T == 0 && is_prime(T)) return "Yes";
for (int i = 2; i * i <= N; ++i) {
if (!is_prime(i)) continue;
int n = N, t = T;
int cnt = 0;
while (n % i == 0) n /= i;
while (t % i == 0) {
t /= i;
++cnt;
}
if (t == 1 && n == 1) {
if (cnt <= 2) return "Yes";
}
}
return "No";
}
};
