CF679A Bear and Prime 100

一. 审题：

1. 前提条件：

  • 无

2. 询问 & 输入：

  • 询问：（最多 2020 次）
    输出一个数 xx，代表询问 xx 是否是被猜数的约数。

  • 输入：
    读入一个字符 yes 或 no 代表这个数是否是被猜数的约数。

3. 输出：

  • 该数是否是素数。

二. 思路

  • 我们知道质数的因数有且只有 11 和自己，也就是 11 和一个质数。所以第一感觉是把 1−1001-100 的质数问一遍。但很快发现询问次数不够。而且也用不着，因为，如果只问 1-50 内的质数：

    1. 如果有2个及以上的 yesyes 回答，直接判断为合数。
    2. 如果有一个 yesyes 回答，51−10051-100 不可能有因数，那样所猜数就超100了。
    3. 如果无 yesyes 回答，51−10051-100 必有且只有一个因数，就是他本身呀。
      所以问 51−10051-100 的质数是无意义的。

  • 问完质数还不够，例如 4 就判断不出来，因为本交互程序只判断有没有这个因数，不能说出该因数个数。所以还得判断质数的平方数（100100 以内的）

三. 代码

因为每个输出后都跟了endl，所以不需要加fflush(stdout)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;

int primes[20] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 
                  37, 41, 43, 47};	//1-50内质数，共15个
int sq_nums[10] = {4, 9, 25, 49};	//质数的平方数(100以内的) 
string feedback;	//交互返回的字符串
bool once;	//是否已经返回过一次yes了
int main() {
    for (int i = 0; i < 15; ++i) {
        cout << primes[i] << endl;
        cin >> feedback;
        if (feedback == "yes") {
            if (!once) {
                once = 1;
            } else {
                cout << "composite" << endl;
                return 0;
            }
        } 
    }
    for (int i = 0; i < 4; ++i) {
        cout << sq_nums[i] << endl;
        cin >> feedback;
        if (feedback == "yes") {//这些平方数本来就是合数，所以只要返回1次yes就可以判断了
            cout << "composite" << endl;
            return 0;			
        }
    }
    cout << "prime" << endl;
    return 0;
}