不一样的猜数游戏

瓦斯亚和皮台亚在玩一个简单的游戏。瓦斯亚心中想一个整数x,它是1n之间的整数。然后皮台亚尝试着猜这个数字。

皮台亚每次问一个形如这样的问题:这个xy的倍数吗?

这个游戏的流程是这样的:首先皮台亚把所有他想问的形如上述的问题都问出来(当然他也可以不问任何问题),然后瓦斯亚针对每一个问题给出yesno的答案。最后皮台亚根据这些问题推断出瓦斯亚心中所想的x是哪个数字。

现在皮台亚想知道他最少要问多少个问题才能猜出1n之间的那个数字。也就是说不管x1n之间的哪个数字只要问那些问题就能够确定那个数字了。

样例解释:

可以问是否是234这些数字倍数的三个问题。

如果都不是,说明是1.

如果是4的倍数,说明是4.

如果是3的倍数说明是3.

否则就是2

没有比这更少的问题数目了。


Input
单组测试数据。
第一行输入一个整数n (1≤n≤1000)。
Output
输出最少的问题数目。
Input示例
样例输入1
4
Output示例
样例输出1
3
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

const int MAXN = 1e3 + 10;
int n;
bool isPrime[MAXN];

void calPrime(int num)
{
	memset(isPrime, true, sizeof(isPrime));
	int maxNum = sqrt(num);
	for (int i = 2; i <= maxNum; i++)
	{
		for (int j = i * i ; j <= num; j += i)
		{
			isPrime[j] = false;
		}
	}
}

int fun(int num)
{
	calPrime(num);
	int result = 0;
	for (int i = 2; i <= num; i++)
	{
		if (isPrime[i])
		{
			result += log(num) / log(i);
		}
	}

	return result;
}

int main()
{
	cin >> n;
	cout << fun(n) << endl;

    return 0;
}
相关文章
相关标签/搜索