题目来源： CodeForces
基准时间限制：1 秒 空间限制：131072 KB 分值: 20 难度：3级算法题
收藏
关注瓦斯亚和皮台亚在玩一个简单的游戏。瓦斯亚心中想一个整数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
#include<bits/stdc++.h>
using namespace std;
bool is_prime[1005];
int a[1005];//素数表
int total[1005];//存储1到n的最大公约数的素数因子分解结果
int main()
{
//暴力筛一遍素数
for(int i=2;i<=1000;i++)
{
bool f=1;
for(int k=2;k*k<=i;k++)
if(i%k==0){f=0;break;}
is_prime[i]=f;
}
int n;
int num=0;
cin>>n;
//生成素数表
for(int i=2;i<=n;i++)if(is_prime[i])a[num++]=i;
int temp=n;
for(int N=temp;N>=2;N--)
{
int thi=N;
for(int i=0;i<num;i++)
{
int MA=total[i];int time=0;
while(N%a[i]==0)time++,N/=a[i];
total[i]=max(total[i],time);
}
N=thi;
}
int ans=0;
for(int i=0;i<num;i++)ans+=total[i];
cout<<ans<<endl;
return 0;
}