PAT_A1116#Come on! Let's C

Source:

Description:

Input Specification:

Output Specification:

Sample Input:

Sample Output:

Keys:

• 素数（Prime）

Attention:

• 对于较大规模的数据，采用打表的方法可以大大的优化时间，平时应该养成习惯已备不时之需；

Code:

 /*

 Data: 2019-06-11 20:19:43

 Problem: PAT_A1116#Come on! Let's C

 AC: 15:40

 题目大意：

 按排名给出N名同学的ID，

 第一名，Mystery Award

 素数名次，Minion

 其他名次，Chocolate

 询问过了，Checked

 占便宜者，Are you kidding?

 */

 #include<cstdio>

 #include<string>

 #include<vector>

 #include<iostream>

 using namespace std;

 const int M=1e5;

 int isPrime[M],n,name;

 string id[M];

 vector<int> prime;

 void Euler()

 {

     fill(isPrime,isPrime+n+,);

     isPrime[]=;isPrime[]=;

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

         if(isPrime[i])

             prime.push_back(i);

         for(int j=; j<prime.size(); j++){

                 if(i*prime[j]>n)

                     break;

                 isPrime[i*prime[j]]=;

                 if(i%prime[j]==)

                     break;

         }

     }

 }

 int main()

 {

 #ifdef    ONLINE_JUDGE

 #else

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

 #endif

     scanf("%d", &n);

     Euler();

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

     {

         scanf("%d", &name);

         if(i == )

             id[name] = "Mystery Award";

         else if(isPrime[i])

             id[name] = "Minion";

         else

             id[name] = "Chocolate";

     }

     scanf("%d", &n);

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

     {

         scanf("%d", &name);

         printf("%04d: ", name);

         if(id[name].size() != ){

             cout << id[name] << endl;

             id[name] = "Checked";

         }

         else

             cout << "Are you kidding?" << endl;

     }

     return ;

 }