結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー かりあげクンかりあげクン
提出日時 2020-09-30 10:10:45
言語 Haskell
(9.8.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,035 bytes
コンパイル時間 152 ms
コンパイル使用メモリ 151,808 KB
最終ジャッジ日時 2024-04-28 09:38:34
合計ジャッジ時間 508 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )

Main.hs:10:1: error: [GHC-87110]
    Could not load module ‘GHC.Integer.GMP.Internals’.
    It is a member of the hidden package ‘integer-gmp-1.1’.
    Use -v to see a list of the files searched for.
   |
10 | import qualified GHC.Integer.GMP.Internals         as GMP
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

ソースコード

diff # 

{-# LANGUAGE BangPatterns #-}
import qualified Control.Arrow                     as Arrow
import           Data.Bits                         (Bits (unsafeShiftL, unsafeShiftR),
                                                    FiniteBits (countTrailingZeros))
import           Data.Bool                         (bool)
import qualified Data.ByteString.Char8             as BSC8
import qualified Data.List                         as List
import qualified Data.Vector.Fusion.Stream.Monadic as MS
import qualified Data.Vector.Unboxed               as VU
import qualified GHC.Integer.GMP.Internals         as GMP
-------------------------------------------------------------------------------
main :: IO ()
main = do
  n <- readLn :: IO Int
  rep n $ \_ -> do
    x <- readLn :: IO Integer
    BSC8.putStrLn $ solve x
solve :: Integer -> BSC8.ByteString
solve n = BSC8.pack $ show n ++ (bool " 0"  " 1" (isPrime n))
-------------------------------------------------------------------------------
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 k
  | k <= 3 = k == 2 || k == 3
  | even k = False
  | otherwise = mr k
  where
    mr :: Int -> Bool
    mr 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 = unsafeShiftR m s
        check3 :: Int -> Bool
        check3 a = powModInt a d n /= 1
        {-# INLINE check3 #-}
        check4 :: Int -> Int -> Bool
        check4 a i = (powModInt a (d * (unsafeShiftL 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)]
-------------------------------------------------------------------------------
rep :: (Monad m) => Int -> (Int -> m ()) -> m ()
rep n = flip MS.mapM_ (stream 0 n)
{-# INLINE rep #-}

stream :: (Monad m) => Int -> Int -> MS.Stream m Int
stream !l !r = MS.Stream step l
  where
    step x
        | x < r = return $ MS.Yield x (x + 1)
        | otherwise = return MS.Done
    {-# INLINE [0] step #-}
{-# INLINE [1] stream #-}

infixl 8 .>>., .<<.
(.>>.) :: Bits i => i -> Int -> i
(.>>.) = unsafeShiftR
{-# INLINE (.>>.) #-}

(.<<.) :: Bits i => i -> Int -> i
(.<<.) = unsafeShiftL
{-# INLINE (.<<.) #-}

powModInt :: Int -> Int -> Int -> Int
powModInt a n mo = fromInteger $ GMP.powModInteger (fromIntegral a) (fromIntegral n) (fromIntegral mo)
{-# INLINE powModInt #-}
0