算法
(交互、素数)
结论:
合数至少有两个不同的素因子或一个素数平方因子
我们只需预处理出前 $50$ 里面的素数和素数平方,并存放到数组 $ps$ 中
对于被隐藏的数 $X$ 而言,如果 $ps$ 中有至少 $2$ 个数可以被 $X$ 整除,那么 $X$ 就是合数,否则 $X$ 就是素数
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::string;
const int ps[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 4, 9, 25, 49};
int main() {
int cnt = 0;
for (int x : ps) {
cout << x << '\n';
string s;
cin >> s;
cnt += s == "yes";
}
puts(cnt >= 2 ? "composite" : "prime") << '\n';
return 0;
}