1536 不一樣的猜數遊戲
基準時間限制：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示例
樣例輸入14
Output示例
樣例輸出13
打表+最小公倍數
代碼：
#include<cstdio>
#include<cstring>
int gcd(int a,int b)
{
if (a%b==0)
return b;
return gcd(b,a%b);
}
int bei(int a,int b)
{
int lp;
if (a>b)
lp=gcd(a,b);
else
lp=gcd(b,a);
lp=a/lp*b;
return lp;
}
int main()
{
int n;scanf("%d",&n);
int ll=0,k,shu[1200];
bool fafe[1200];
memset(fafe,true,sizeof(fafe));
for (int i=2;i<=n;i++)
{
if (fafe[i])
{
shu[ll++]=i;
fafe[i]=false;
for (int j=2;j<=n;j++)
{
if (!fafe[j])
{
k=bei(j,i);
if (k<=n)
fafe[k]=false;
}
}
}
}
printf("%d\n",ll);
return 0;
}