結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー かりあげクンかりあげクン
提出日時 2020-09-15 11:32:09
言語 Haskell
(9.8.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,284 bytes
コンパイル時間 487 ms
コンパイル使用メモリ 163,256 KB
最終ジャッジ日時 2023-08-11 23:06:54
合計ジャッジ時間 921 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ（β）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

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

Main.hs:51:39: error: [GHC-76037]
    Not in scope: ‘GMP.powModWord’
    NB: the module ‘GHC.Integer.GMP.Internals’ does not export ‘powModWord’.
    Suggested fix: Perhaps use ‘Main.powModWord’ (line 51)
   |
51 | powModWord (W# x) (W# y) (W# m) = W# (GMP.powModWord x y m)
   |                                       ^^^^^^^^^^^^^^

ソースコード

diff # 

{-# LANGUAGE MagicHash #-}
import qualified Control.Arrow             as Arrow

import           Data.Bool                 (bool)
import           Data.Bits

import qualified Data.ByteString.Char8     as BSC8

import qualified Data.Vector.Unboxed       as VU

import           GHC.Exts
import           GHC.Natural

import qualified GHC.Integer.GMP.Internals as GMP

isPrime :: Int -> Bool
isPrime k
  | k <= 3 = k == 2 || k == 3
  | even k = False
  | otherwise = millerRabin k
  where
    millerRabin :: Int -> Bool
    millerRabin 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 `unsafeShiftR` s

        loop [] = True
        loop (a:as)
          | (powModInt (a `mod` n) d n /= 1) && allok = False
          | otherwise = loop as
          where
            allok = all (\r -> (powModInt a ((1 `unsafeShiftL` r) * d) n) /= m) [0..(s - 1)]

powModInteger :: Integer -> Integer -> Integer -> Integer
powModInteger b e m = GMP.powModInteger (b `mod` m) e m
{-# INLINE powModInteger #-}

powModWord :: Word -> Word -> Word -> Word
powModWord (W# x) (W# y) (W# m) = W# (GMP.powModWord x y m)
{-# INLINE powModWord #-}

powModInt :: Int -> Int -> Int -> Int
powModInt x y m
  | m <= 0 = error "powModInt: non-positive modulo"
  | y <  0 = error "powModInt: negative exponent"
  | otherwise = wordToInt $ powModWord (intToWord (x `mod` m)) (intToWord y) (intToWord m)
{-# INLINE powModInt #-}

wordToInt :: Word -> Int
wordToInt = fromIntegral
{-# INLINE wordToInt #-}

wordToInteger :: Word -> Integer
wordToInteger = fromIntegral
{-# INLINE wordToInteger #-}

intToWord :: Int -> Word
intToWord = fromIntegral
{-# INLINE intToWord #-}

intToInteger :: Int -> Integer
intToInteger = fromIntegral
{-# INLINE intToInteger #-}

naturalToInteger :: Natural -> Integer
naturalToInteger = fromIntegral
{-# INLINE naturalToInteger #-}

integerToNatural :: Integer -> Natural
integerToNatural = fromIntegral
{-# INLINE integerToNatural #-}

integerToWord :: Integer -> Word
integerToWord = fromIntegral
{-# INLINE integerToWord #-}

integerToInt :: Integer -> Int
integerToInt = fromIntegral
{-# INLINE integerToInt #-}

type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString)
parseInt :: Parser Int
parseInt = fmap (Arrow.second BSC8.tail) . BSC8.readInt
parse1 :: IO Int
parse1 = readLn
parseN :: Int -> IO (VU.Vector Int)
parseN n = VU.replicateM n parse1
-------------------------------------------------------------------------------
main :: IO ()
main = do
  n  <- parse1
  xs <- parseN n
  VU.mapM_ (BSC8.putStrLn . solve) xs

solve :: Int -> BSC8.ByteString
solve n = BSC8.pack $ bool (show n ++ " 0") (show n ++ " 1") (isPrime n)
-------------------------------------------------------------------------------
0