import Control.Monad (liftM)
import Data.Bits (Bits, testBit, shiftR)
import System.Random (Random, getStdGen, randomRs)
import System.IO.Unsafe (unsafePerformIO)
import Prelude hiding (even, odd)

odd :: (Integral a, Bits a) => a -> Bool
odd = (`testBit` 0)

even :: (Integral a, Bits a) => a -> Bool
even = not . odd

-- modPow - Recursive modular exponentiation by taking successive powers of two
modPow :: (Integral a, Bits a) => a -> a -> a -> a
modPow _ 0 _ = 1
modPow base ex m = let term
                         | testBit ex 0 = base `mod` m
                         | otherwise    = 1
                   in (term * modPow (base^2 `mod` m) (ex `shiftR` 1) m) `mod` m

isPrime :: (Integral a, Bits a, Random a) => a -> a -> Bool
isPrime n k
    | n < 4     = if n > 1 then True else False -- Deal with 0-3.
    | even n    = False
    | otherwise = let randPool = unsafePerformIO $ randNums (n - 2)
                  in witness k randPool
    where
        randNums upper = do
            g <- getStdGen
            return (randomRs (2, upper) g)

        (d, r) = let decompose d r
                        | odd d     = (d, r)
                        | otherwise = decompose (d `shiftR` 1) (r + 1)
                 in decompose (n - 1) 0

        witness 0 _ = True
        witness k (a:rands)
            | x == 1 || x == n - 1 = witness (k - 1) rands
            | otherwise            = check x (r - 1)
            where
                x = modPow a d n

                check _ 0 = False
                check x count
                    | x' == 1     = False
                    | x' == n - 1 = witness (k - 1) rands
                    | otherwise   = check x' (count - 1)
                    where x' = modPow x 2 n

-- main function for testing
main :: IO()
main = do
    [n,k] <- liftM (map (\x -> read x :: Integer) . words) getLine
    print $ isPrime n k