409621: GYM103647 D Parrot Riddles

After an arduous journey through pirate-infested waters, you have finally reached the legendary treasure of Long John Silver. Before you can open the treasure chest, Long John Silver's trusty parrot, Captain Flint swoops down and demands that you solve his math riddle to prove you are worthy of the vast gold Long John Silver left behind. (Below are multiple interpretations of Captain Flint)

Captain Flint tells you that he is currently thinking of a number $$$n$$$ between $$$2$$$ and $$$100$$$ (inclusive). You find out that you may ask him up to $$$20$$$ queries to figure out if the number that he is thinking of is prime or composite. If you guess wrong, give an invalid query, or try to use too many queries, he will tell Long John Silver that you are stealing his gold and Long John Silver is highly protective of his stash so this would not be good.

Captain Flint lets you ask queries of the following type: you can give him a number $$$i$$$ between $$$2$$$ and $$$100$$$ (inclusive) and he will tell you if $$$n$$$ is divisible by $$$i$$$. Given that you have traveled this far for this treasure you want to be absolutely sure that you get the treasure so write an interactive program to determine if Captain Flint's number $$$n$$$ is prime or not.

You can ask a query of the form ? i up to $$$20$$$ times where $$$2 \leq i \leq 100$$$. Make sure that when you print the query you include the end of line character and flush the output. In response, you will receive the string yes if $$$n$$$ is divisible by $$$i$$$ and no otherwise.

When you think you know whether or not $$$n$$$ is prime, you print the answer in the form ! prime if $$$n$$$ is prime and ! composite if not and then stop your program.

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

• fflush(stdout) in C++;
• System.out.flush() in Java;
• stdout.flush() in Python;

no
yes
yes

? 50
? 2
? 15
! composite

In the given example, $$$n$$$ is $$$30$$$ so for the first query, $$$50$$$ is not a divisor of $$$30$$$ so it prints no. Then, the next two queries are both divisors of $$$30$$$ so it prints yes both times at which point you know that $$$n$$$ must be composite.