Little Olaf has two piggy banks. Every day he puts one Euro in one of the banks until each bank
contains N Euros. Then he can buy a new toy.
Little Olaf also likes prime numbers. Sometimes, the amount of Euros in the first bank concatenated
with the amount of Euros in the second bank is a prime number. For example, if the first bank contains
12 Euros and the second bank contains 7 Euros, the concatenation 127 is a prime number.
Your task is to find an optimal order to put the Euros in the banks so that as many prime numbers as
possible appear. Initially, each bank contains 1 Euro.
Here is one order to fill the banks when N = 4:
Note that the initial 11 is not counted!
The only line of input contains one integer N: the number of Euros that each piggy bank should
finally contain.
1 ≦ N ≦ 999
The only line of output should contain one integer: the number of prime numbers in an optimal filling
order.
4 14 25
3 12 21
Migrated from old NTUJ.
BOI2011 Practice Day
No. | Testdata Range | Score |
---|