CF-679A-Bear-and-Prime-100

发表于   |     |   阅读次数

题意：有一个隐藏数字N，2<=N<=100。要求在20次查询后，确定N是否为支数。
每一次你可以输出一个数字a，系统会判定a是否为N的除数（YES or NO）。

思路：N只有两种可能，合数或质数。
其中，质数是的除数只有1和本身。合数的除数至少有3个（1，本身，K）。
因此，合数=质数*质数。
所以，可以枚举小于50的所有质数，依次询问这些质数是否为N的除数，如果是除数的次数>=2，则即可判定为合数。

注意点：2^n,3^n,5^n,7^n,都是有相同的质数乘积得到。所以按照上面的逻辑判断后，最后得到次数只有1次。
显然是错误的，因此需要再添加4，9，15，49。
因此，最会需要查询的数字包括[2,3,4,5,7,9,11,13,17,19,23,25,29,31,37,41,43,47,49];

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
#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;

int main()
{
	//freopen("in.txt", "r", stdin);
	int num[] = {2,3,4,5,7,9,11,13,17,19,23,25,29,31,37,41,43,47,49};
	string str;
	int cnt = 0;
	for (int i = 0; i < 19; ++i)
	{
		cout<<num[i]<<endl;
		cin>>str;
		if(str == "yes")
			cnt++;
	}
	if(cnt >=2)
		cout<<"composite"<<endl;
	else
		cout<<"prime"<<endl;
	//fclose(stdin);  
	return 0;
}