#P17496. [ICPC 2026 Wuhan I] Prime Game
[ICPC 2026 Wuhan I] Prime Game
Problem Description
Iroha and Kaguya have recently become fascinated by a mathematical game based on integers.
Initially, they share a positive integer . The two players take turns performing operations; a single round is defined as both Iroha and Kaguya completing one operation each. In each round:
- Iroha goes first: She must choose a non-negative integer () and replace the current with .
- Kaguya goes second: She must choose a prime number that divides the current (i.e., ) and replace the current with .
The above operations repeat continuously. If after the end of any round, the game ends immediately.
During the game, Iroha aims to maximize the total number of rounds played, while Kaguya aims to minimize the total number of rounds. Assuming both players are perfectly rational and adopt optimal strategies, please determine the total number of rounds the game will ultimately last.
Input Format
The first line contains an integer (), representing the initial number of the game.
Output Format
Output a single line containing an integer, representing the total number of rounds the game will last given that both players play optimally.
1
0
9
4
16
5