C. Bear and Prime 100

This is an interactive problem. In the output section below you will see the information about flushing the output.

Bear Limak thinks of some hidden number — an integer from interval [2, 100]. Your task is to say if the hidden number is prime or composite.

Integer x > 1 is called prime if it has exactly two distinct divisors, 1 and x. If integer x > 1 is not prime, it’s called composite.

You can ask up to 20 queries about divisors of the hidden number. In each query you should print an integer from interval [2, 100]. The system will answer “yes” if your integer is a divisor of the hidden number. Otherwise, the answer will be “no”.

For example, if the hidden number is 14 then the system will answer “yes” only if you print 2, 7 or 14.

When you are done asking queries, print “prime” or “composite” and terminate your program.

You will get the Wrong Answer verdict if you ask more than 20 queries, or if you print an integer not from the range [2, 100]. Also, you will get the Wrong Answer verdict if the printed answer isn’t correct.

You will get the Idleness Limit Exceeded verdict if you don’t print anything (but you should) or if you forget about flushing the output (more info below).

Input

After each query you should read one string from the input. It will be “yes” if the printed integer is a divisor of the hidden number, and “no” otherwise.

Output

Up to 20 times you can ask a query — print an integer from interval [2, 100] in one line. You have to both print the end-of-line character and flush the output. After flushing you should read a response from the input.

In any moment you can print the answer “prime” or “composite” (without the quotes). After that, flush the output and terminate your program.

To flush you can use (just after printing an integer and end-of-line):

fflush(stdout) in C++; System.out.flush() in Java; stdout.flush() in Python; flush(output) in Pascal; See the documentation for other languages. Hacking. To hack someone, as the input you should print the hidden number — one integer from the interval [2, 100]. Of course, his/her solution won’t be able to read the hidden number from the input.

Examples

input

yes

no

yes

output

2

80

5

composite

input

no

yes

no

no

no

output

58

59

78

78

2

prime

Note

The hidden number in the first query is 30. In a table below you can see a better form of the provided example of the communication process. The hidden number is divisible by both 2 and 5. Thus, it must be composite. Note that it isn’t necessary to know the exact value of the hidden number. In this test, the hidden number is 30. 59 is a divisor of the hidden number. In the interval [2, 100] there is only one number with this divisor. The hidden number must be 59, which is prime. Note that the answer is known even after the second query and you could print it then and terminate. Though, it isn’t forbidden to ask unnecessary queries (unless you exceed the limit of 20 queries).

Solution

At first I didn’t understand the problem’s meaning. ;-(

In fact, the problem means:

Write a program to guess a number a time, the user input yes or no: if the displayed number is divisible by the unknown number, the user will input yes, otherwise, the user will input no. You program can’t guess more than 20 times. Your program must output prime or composite if you can determin whether the number is prime. You must determin this in 20 times guesses. Besides, the unknown number is in [2, 100].

A composite number is either divisible by p^2 for some prime p, or divisible by two distinct prime numbers p and q. a. if the number is divisible by p^2 for some prime p, we can know that p must be in 2 3 5 7, because the unknown number is not more than 100. If p is divisible by the number, we must guess p * p again. b. if the number is divisible by two distinct prime numbers p and q, suppose p < q. Because p >= 2, p * q <= 100, then q < 50. then we can iterate q in prime numbers below 50.

we know that prime numbers below 50 is:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

there are 15 prime numbers below 50.

In the first case, there are at most 8 guesses. In the second case, there are at most 15 - 4 = 11 guesses. So there are at most 19 guesses in all. 19 < 20, it satisifies the problem.

Code

/*
 * =====================================================================================
 *
 *       Filename:  c.cpp
 *
 *    Description:  
 *
 *        Version:  1.1
 *        Created:  06/10/2016 08:57:54 PM
 *       Compiler:  g++
 *
 *         Author:  Sabastian (liuxueyang.github.io), liuxueyang457@gmail.com
 *
 * =====================================================================================
 */
#include <bits/stdc++.h>
using namespace std;
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define rep(i, a, n) for (int i = a; i < n; ++i)
#define per(i, a, n) for (int i = n-1; i > a; --i)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef map<int,int> MI;
typedef long long ll;
typedef pair<int,int> PII;
//const ll mod=1000000007;
bool isPrime(int n) {

  for ( int i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}

bool isDivisible(int n) {
  string str;
  printf ( "%d\n", n );
  fflush(stdout);
  cin >> str;
  return str == "yes";
}

int a[50];
  int
main ( void )
{
#ifndef  ONLINE_JUDGE
//  freopen("c.in", "r", stdin);
#endif     /* -----  ONLINE_JUDGE  ----- */

  int j = 0;
  rep(i, 2, 51) {
    if (isPrime(i)) {
      a[j] = i;
      ++j;
    }
  }
  rep(i, 0, j) {
    printf ( "%d ", a[i] );
  }
  printf ( "\n" );
  // j is len
  // a. 2, 3, 5, 7 -> ... 
  // b. primes less than 50

  string str;
  int cnt = 0;
  rep (i, 0, j) {
    if ( isDivisible(a[i]) ) {
      ++cnt;
      if ( cnt >= 2 ) {
        printf ( "composite\n" );
        fflush(stdout);
        return EXIT_SUCCESS;
      }
      if ( a[i] <= 7 && isDivisible(a[i] * a[i])) {
        ++cnt;
      }
      if ( cnt >= 2 ) {
        printf ( "composite\n" );
        fflush(stdout);
        return EXIT_SUCCESS;
      }
    }
  }
  printf ( "prime\n" );
  fflush(stdout);

  return EXIT_SUCCESS;
}				/* ----------  end of function main  ---------- */