题意:有一个隐藏数字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 |
|