現在有一個數x，1 ≤ x≤ n，告訴你n，每次你可以猜一個數y，如果x==y則結束，否則返回gcd(x,y)，問最少只要幾次就可以保證猜出答案。
Input
The input file contains several test cases, each of them as described below.
The input contains one integer n, 2n10000.
Output
For each test case, write to the output on a line by itself.
Output one integer -- the number of guesses Andrew will need to make in the worst case.
Sample Input
6
Sample Output
2
首先把所有n以內素分組，每次詢問一組素數的積——根據Gcd的性質確定這個數
每次貪心拿一個大質數與一堆小質數配（最右X最左）
[cpp]
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cstdlib>
#include<cmath>
using namespace std;
#define MAXN (10000)
#define eps (1e-9)
#define For(i,n) for(int i=1;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
int n,a[MAXN],size=0;
bool b[MAXN];
int main()
{
memset(b,0,sizeof(b));b[1]=1;
Fork(i,2,MAXN)
{
if (!b[i]) b[i]=1,a[++size]=i;
For(j,size)
{
if (i*a[j]>MAXN) break;
b[i*a[j]]=1;
if (!i%a[j]) break;
}
}
// For(i,100) cout<<a[i]<<' ';
while (cin>>n)
{
int i=0,head=1,tail=size;
while (a[tail]>n) tail--;
while (head<=tail)
{
int p=a[tail];
while (p*a[head]<=n) p*=a[head++];
tail--;i++;
}
cout<<i<<endl;
}
return 0;
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cstdlib>
#include<cmath>
using namespace std;
#define MAXN (10000)
#define eps (1e-9)
#define For(i,n) for(int i=1;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
int n,a[MAXN],size=0;
bool b[MAXN];
int main()
{
memset(b,0,sizeof(b));b[1]=1;
Fork(i,2,MAXN)
{
if (!b[i]) b[i]=1,a[++size]=i;
For(j,size)
{
if (i*a[j]>MAXN) break;
b[i*a[j]]=1;
if (!i%a[j]) break;
}
}
// For(i,100) cout<<a[i]<<' ';
while (cin>>n)
{
int i=0,head=1,tail=size;
while (a[tail]>n) tail--;
while (head<=tail)
{
int p=a[tail];
while (p*a[head]<=n) p*=a[head++];
tail--;i++;
}
cout<<i<<endl;
}
return 0;
}
