Time Limit: 1000ms
Memory Limit: 65536kb
DescriptionMr. Geek is a geek through-and-through. In his Twitter, he revealed that his idol is Sheldon. Birds of a feather flock together. His girlfriend is also a geek
As we all know, USTCers love wearing clothes with the logo of USTC printed. As the summer is coming, Mr. Geek decides to hold a big T-shirt party in USTC. His girlfriend Amy is in charge of the placing of T-shirts.
Amy wants to find the most lovely width and height of the T-shirt grid. The term “most lovely” is defined as follows. (Yep, she is also a geek through-and-through.) She has m (greater than 4) T-shirts, at least 4 of them should be on show. A positive fraction a/b less than or equal to 1 is also given. The ratio of the width to the height should not be less than a/b nor greater than 1. What’s more, Amy loves prime number, so she hopes that both the width and height are prime numbers. Amy wants to show as much T-shirts as possible under these constraints, and she turns to Mr. Geek for help.
Mr. Geek is busy preparing GRE, so he turns to you for help. He hopes that you can determine the most lovely width and height of the T-shirt grid.
For example, Amy has 30 T-shirts. And a=2, b=5. The most lovely width=5, the height=5.
All the T-shirts:
The most lovely grid (5*5):
InputThe input consists of one or more test cases, followed by a line containing the number 0 0 0 that signals the end of the input.
Each test case is a single line containing a positive integer m, the numerator a, and the denominator b described above. (4 < m <= 100000, 1 <= a <= b <= 1000.)
OutputFor each test case you should output the most lovely width and height of the T-shirt grid.
2011 3 6 31 3 7 127 7 31 8191 31 127 0 0 0
37 53 5 5 11 11 79 103