{-# LANGUAGE BangPatterns #-} import Data.Bits (Bits (unsafeShiftL, unsafeShiftR), FiniteBits (countTrailingZeros)) import qualified GHC.Integer.GMP.Internals as GMP main :: IO () main = do n <- readLn :: IO Integer if n < 50 then putStrLn $ ["0","1","2","3","3","5","5","7","7","7","7","11","11","13","13","7","7","17","8","19","19","19","7","23","23","23","8","8","8","29","8","31","8","8","8","8","8","37","8","8","8","41","8","43","8","8","8","47","8","14","8"] !! (fromInteger n) else if n `mod` 8 == 1 && isPrime (n - 8) then putStrLn "14" else putStrLn "8" isPrime :: Integer -> Bool isPrime k | k <= 3 = k == 2 || k == 3 | even k = False | otherwise = millerRabin k where millerRabin :: Integer -> Bool millerRabin n | n < 18446744073709551616 = millerRabinSmall (fromInteger n) | n < 318665857834031151167461 = loop [2,3,5,7,11,13,17,19,23,29,31,37] | otherwise = loop [2,3,5,7,11,13,17,19,23,29,31,37,41] where !m = n - 1 !s = cTZ m 0 !d = m .>>. s cTZ :: Integer -> Int -> Int cTZ !i !cnt | odd i = cnt | otherwise = cTZ (i .>>. 1) (cnt + 1) {-# INLINE cTZ #-} check1 :: Integer -> Bool check1 a = GMP.powModInteger a d n /= 1 {-# INLINE check1 #-} check2 :: Integer -> Int -> Bool check2 a i = (GMP.powModInteger a (d * (1 .<<. i)) n) /= m {-# INLINE check2 #-} loop [] = True loop (a:as) | check1 a && allok = False | otherwise = loop as where allok = all (check2 a) [0..(s - 1)] millerRabinSmall :: Int -> Bool millerRabinSmall n | n < 2047 = loop [2] | n < 1373653 = loop [2,3] | n < 9080191 = loop [31,73] | n < 25326001 = loop [2,3,5] | n < 4759123141 = loop [2,7,61] | n < 1122004669633 = loop [2,13,23,1662803] | n < 2152302898747 = loop [2,3,5,7,11] | n < 3474749660383 = loop [2,3,5,7,11,13] | n < 341550071728321 = loop [2,3,5,7,11,13,17] | otherwise = loop [2,325,9375,28178,450775,9780504,1795265022] where !m = n - 1 !s = countTrailingZeros m !d = m .>>. s check3 :: Int -> Bool check3 a = powModInt a d n /= 1 {-# INLINE check3 #-} check4 :: Int -> Int -> Bool check4 a i = (powModInt a (d * (1 .<<. i)) n) /= m {-# INLINE check4 #-} loop [] = True loop (a:as) | check3 a && allok = False | otherwise = loop as where allok = all (check4 a) [0..(s - 1)] powModInt :: Int -> Int -> Int -> Int powModInt a n mo = fromInteger $ GMP.powModInteger (fromIntegral a) (fromIntegral n) (fromIntegral mo) {-# INLINE powModInt #-} infixl 8 .>>., .<<. (.>>.) :: Bits i => i -> Int -> i (.>>.) = unsafeShiftR {-# INLINE (.>>.) #-} (.<<.) :: Bits i => i -> Int -> i (.<<.) = unsafeShiftL {-# INLINE (.<<.) #-}