51nod1536 不一样的猜数游戏（思考题目的乐趣）

125 阅读 0 评论 83 点赞

我是靠谱客的博主跳跃苗条，这篇文章主要介绍51nod1536 不一样的猜数游戏（思考题目的乐趣），现在分享给大家，希望可以做个参考。

1536 不一样的猜数游戏
瓦斯亚和皮台亚在玩一个简单的游戏。瓦斯亚心中想一个整数x，它是1到n之间的整数。然后皮台亚尝试着猜这个数字。
皮台亚每次问一个形如这样的问题：这个x是y的倍数吗？
这个游戏的流程是这样的：首先皮台亚把所有他想问的形如上述的问题都问出来（当然他也可以不问任何问题），然后瓦斯亚针对每一个问题给出yes或no的答案。最后皮台亚根据这些问题推断出瓦斯亚心中所想的x是哪个数字。
现在皮台亚想知道他最少要问多少个问题才能猜出1到n之间的那个数字。也就是说不管x是1到n之间的哪个数字只要问那些问题就能够确定那个数字了。
样例解释：
可以问是否是2，3，4这些数字倍数的三个问题。
如果都不是，说明是1.
如果是4的倍数，说明是4.
如果是3的倍数说明是3.
否则就是2。
没有比这更少的问题数目了。

Input
单组测试数据。
第一行输入一个整数n (1≤n≤1000)。
Output
输出最少的问题数目。
Input示例
样例输入1
4
Output示例
样例输出1
3

复制代码

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
33
34
35
36
37
38
39
40
41
42
43
/**
*这个题我们应该怎么想呢？
*对于每一个整数，都可以由素数构造而成，
*因此这个素数的能使用的次数的个数都要询问到，
*最后的结构就是所有素数的次方的和
*
*/
#include<iostream>
using namespace std;
int prime[1001];
bool is_prime(int n){
if(n==2) return true;
for(int i=2;i*i<=n;i++){
if(n%i==0) return false;
}
return true;
}
int getQueryNum(int n){
if(n==1) return 0;
int k = 0;
for(int i=2;i<=n;i++){
if(is_prime(i)) prime[k++] = i;
}
int ans = 0;
for(int i=0;i<k;i++){
int p = 0,tmp = prime[i];
while(tmp <= n){
p++;
tmp *= prime[i];
}
ans += p;
}
return ans;
}
int main()
{
int n;
while(cin>>n){
cout<<getQueryNum(n)<<endl;
}
return 0;
}