結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー かりあげクンかりあげクン
提出日時 2020-09-30 10:10:45
言語 Haskell
(9.6.2)
結果
AC  
実行時間 223 ms / 9,973 ms
コード長 4,035 bytes
コンパイル時間 931 ms
コンパイル使用メモリ 198,892 KB
実行使用メモリ 12,964 KB
最終ジャッジ日時 2023-08-10 16:25:32
合計ジャッジ時間 2,714 ms
ジャッジサーバーID
(参考情報)
judge14 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
7,856 KB
testcase_01 AC 2 ms
7,672 KB
testcase_02 AC 3 ms
8,024 KB
testcase_03 AC 3 ms
8,284 KB
testcase_04 AC 152 ms
12,888 KB
testcase_05 AC 152 ms
12,852 KB
testcase_06 AC 102 ms
12,740 KB
testcase_07 AC 102 ms
12,960 KB
testcase_08 AC 102 ms
12,808 KB
testcase_09 AC 223 ms
12,964 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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:42:20: warning: [GHC-68441] [-Wdeprecations]
    In the use of ‘powModInteger’
    (imported from GHC.Integer.GMP.Internals):
    Deprecated: "Use integerPowMod# instead"
   |
42 |         check1 a = GMP.powModInteger a d n /= 1
   |                    ^^^^^^^^^^^^^^^^^

Main.hs:45:23: warning: [GHC-68441] [-Wdeprecations]
    In the use of ‘powModInteger’
    (imported from GHC.Integer.GMP.Internals):
    Deprecated: "Use integerPowMod# instead"
   |
45 |         check2 a i = (GMP.powModInteger a (d * (1 .<<. i)) n) /= m
   |                       ^^^^^^^^^^^^^^^^^

Main.hs:112:34: warning: [GHC-68441] [-Wdeprecations]
    In the use of ‘powModInteger’
    (imported from GHC.Integer.GMP.Internals):
    Deprecated: "Use integerPowMod# instead"
    |
112 | powModInt a n mo = fromInteger $ GMP.powModInteger (fromIntegral a) (fromIntegral n) (fromIntegral mo)
    |                                  ^^^^^^^^^^^^^^^^^
[2 of 2] Linking a.out

ソースコード

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