SRM517 Div1 Easy - CompositeSmash

問題

数字nが書かれたボールを殴ると、nが合成数であるとき、dとn/dが書かれた2つのボールに分裂する(d:ランダムなnの約数)
合成数でないときは何も起こらない
何度でもボールを殴れるとき、数字tが書かれたボールを必ず作ることができるかを判定

解法

t=nならもちろんYes
tがnの素因数ならボールを永遠に殴ってればいつか絶対tになるからYes
あとサンプル1みたいにnの素因数が1種類(=pとする)しかなく、n>=p*pかつt=p*pのときもYesになる
それ以外はNo

class CompositeSmash {
	public:
	vector<int> pf(ll n) {
		vector<int> res;
		for (ll i = 2; i*i <= n; i++) {
			while (n%i==0) {
				res.push_back(i);
				n /= i;
			}
		}
		if (n!=1) res.push_back(n);
		res.erase(unique(all(res)), res.end());
		return res;
	}
	
	string thePossible(int n, int t) {
		vector<int> p = pf(n);
		if (n==t || count(all(p),t) || (p.size()==1 && p[0]*p[0]<=n && t==p[0]*p[0])) return "Yes";
		return "No";
	}
};