Largest Prime Factor

Given an integer \(n\), your task is to compute its largest prime factor. A prime factor of \(n\) is a prime number that divides \(n\) without leaving a remainder. For example, if \(n = 15\), its prime factors are 3 and 5, and the largest prime factor is 5.

The solution should read the input from stdin and output the answer to stdout.

Note: The process should efficiently factorize \(n\), considering that \(n\) might be reduced by first removing the factor 2 and then testing odd numbers up to \(\sqrt{n}\).

inputFormat

The input consists of a single integer \(n\) provided via stdin.

outputFormat

The output is a single integer representing the largest prime factor of \(n\), which should be printed to stdout.

15

5