-- yukicoder My Practice
-- author: Leonardone @ NEETSDKASU

main = readLn >>= print . f where
    f x = g 3 where
        h
            | d > 2 && m == 0 = d
            | otherwise       = x
            where
                (d, m) = divMod x 2
        g i
            | mod x i == 0 = i
            | i * i > x    = h
            | otherwise    = g $ i + 1