문제1805--Piggy Banks

1805: Piggy Banks

실행시간 제한: 5 Sec  메모리사용 제한: 128 MB
제출: 70  통과: 29
[제출] [채점기록] [묻고답하기]

문제 설명

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:

1 , 1 ⇒ 2 , 1 ⇒ 2 , 2 ⇒ 3 , 2 ⇒ 3 , 3 ⇒ 4 , 3 ⇒ 4 , 4

Only one prime number appears: 43. The following order is much better:

1 , 1 ⇒ 2 , 1 ⇒ 3 , 1 ⇒ 4 , 1 ⇒ 4 , 2 ⇒ 4 , 3 ⇒ 4 , 4

Now three prime numbers appear: 31, 41, and 43. This is an optimal filling order for 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.

입력 예시 Copy

4

출력 예시 Copy

3

도움

Sample Input 2

14

Sample Output 2

12

출처/분류