LA 5916(易做图 Guessing Game-质数分组)
现在有一个数x，1 ≤ x≤ n，告诉你n，每次你可以猜一个数y，如果x==y则结束，否则返回易做图(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;
}
补充：软件开发 , C++ ,
