ACM ICPC 2011-2012 Northeastern European Regional Contest（NEERC）G GCD Guessing Game

　　要你去才Paul的年龄，Paul的年龄在1~n之间，你每猜一个Paul会告诉你，你猜的这个数和他年龄的gcd，问在最坏情况下最少要猜多少次。

题解：

　　什么是最坏情况，我们直到如果他的年龄是1的话，你需要猜一边全部素数。所以很明显这就是最坏情况，

　　如果p，q是素数，p*q<=n，我们就可以猜p*q，一次就可以去掉两个素数了。

　　所以这一题就变成了将1~n的素数分成m部分，每一部分的乘积要小于等于n。

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <cmath>

 #include <ctime>

 #include <vector>

 #include <queue>

 #include <map>

 #include <stack>

 #include <set>

 using namespace std;

 typedef long long LL;

 typedef unsigned long long uLL;

 #define ms(a, b) memset(a, b, sizeof(a))

 #define pb push_back

 #define mp make_pair

 #define eps 0.0000000001

 #define IOS ios::sync_with_stdio(0);cin.tie(0);

 #define random(a, b) rand()*rand()%(b-a+1)+a

 const LL INF = 0x3f3f3f3f3f3f3f3f;

 const int inf = 0x3f3f3f3f;

 const int maxn = +;

 const int mod = 1e9+;

 int prime[maxn];

 int main() {

 #ifdef LOCAL

     freopen("input.txt", "r", stdin);

 //    freopen("output.txt", "w", stdout);

 #endif

     freopen("gcd.in", "r", stdin);

     freopen("gcd.out", "w", stdout);

 //    IOS

     int n;

     scanf("%d", &n);

     ms(prime, );

     for(int i = ;i<=n;i++){

         if(!prime[i])   prime[++prime[]] = i;

         for(int j = ;j<=prime[]&&prime[j]<=n/i;j++){

             prime[prime[j]*i] = ;

             if(i%prime[j]==)   break;

         }

     }

     int L = , R = prime[];

     int ans = ;

     while(L<=R){

         int p = prime[R];

         while(prime[L]*p<=n){

             p *= prime[L];

             L++;

         }

         ans++;

         R--;

     }

     printf("%d\n", ans);

     return ;

 }