KUPC 2014 B - 数当てゲーム

問題

1以上1000以下の整数の秘密の数を当てる。
質問は200回まですることができて、質問では、
好きな自然数xに対して、秘密の数がxの倍数かどうかを聞くことができる。


秘密の数を当てよ。

方針

素数ごとにyes, noを聞く。
もし素数pでyesだったら、p^2, p^3, ...とnoになるまで聞く。

で、素数ごとにp^kまでがyesだったらp^kを全部掛ければよい。

ソースコード

const int MX = 1001;
bool p[MX];

int main(){
	
	for(int i = 2; i * i < MX; i++) if(!p[i]) for(int j = i * i; j < MX; j += i) p[j] = 1;
	int ans = 1;
	
	for(int i = 2; i < MX; i++) if(!p[i]){
		for(ll j = i; ans * i < MX; j *= i){
			cout << "? " << j << endl;
			string s; cin >> s;
			if(s == "Y") ans *= i;
			else break;
		}
	}
	cout << "! " << ans << endl;
	
	return 0;
}