Informatica Online Judge

  수 제거 수열 [1175 / 0497]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 26   Total Tried : 34


The Champion of this Problem (C++) : gs15120 - 0ms / 1196byte
My Best Submission (C++) : N/A

[koistudy.net (31st 박정훈)]

Background

1~n까지 n개의 수가 주어져 있다.

여러번 시행을 하는데 한번 시행은 다음과 같다.

만약 남아있는 수의 개수가 소수이면, 맨앞의 수를 지운다.

만약 남아있는 수의 개수가 소수가 아니면(합성수 일때) 남아있는 수의 개수의 가장 작은 소인수를 p라고 했을때, 남아있는 수들 중에서 p의 배수번째에 있는 수들을 모두 제거한다.

마지막에 한 수가 남을때 까지 한 시행의 횟수 f(n)을 구하는 프로그램을 작성하시오.

다음 그림은 n = 7일 때의 예이다.

Input

첫째 줄에 n이 주어진다.

[입력값의 정의역]
1 <= n <= 2^40

Output

이때 f(n)의 값을 출력한다.

IO Example

입력 1
10

출력 1
4

입력 2
7

출력 2
4

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]