結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー かりあげクンかりあげクン
提出日時 2020-10-02 17:59:48
言語 Haskell
(9.6.2)
結果
WA  
実行時間 -
コード長 3,039 bytes
コンパイル時間 1,126 ms
コンパイル使用メモリ 206,684 KB
実行使用メモリ 12,092 KB
最終ジャッジ日時 2023-08-11 23:11:19
合計ジャッジ時間 2,837 ms
ジャッジサーバーID
(参考情報)
judge12 / judge11
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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:75:34: warning: [GHC-68441] [-Wdeprecations]
    In the use of ‘powModInteger’
    (imported from GHC.Integer.GMP.Internals):
    Deprecated: "Use integerPowMod# instead"
   |
75 | powModInt a n mo = fromInteger $ GMP.powModInteger (fromIntegral a) (fromIntegral n) (fromIntegral mo)
   |                                  ^^^^^^^^^^^^^^^^^
[2 of 2] Linking a.out

ソースコード

diff #

{-# LANGUAGE BangPatterns      #-}
{-# LANGUAGE OverloadedStrings #-}
import qualified Control.Arrow                     as Arrow
import           Data.Bits                         (Bits (unsafeShiftL, unsafeShiftR),
                                                    FiniteBits (countTrailingZeros))
import qualified System.IO                         as SysIO
import           Data.Bool                         (bool)
import qualified Data.ByteString.Builder           as BSB
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
  ps <- VU.map isPrime <$> parseN n
  BSB.hPutBuilder SysIO.stdout . VU.foldr ((<>) . bool (BSB.string8 "0\n") (BSB.string8 "1\n")) mempty $ ps
-------------------------------------------------------------------------------
isPrime :: Int -> Bool
isPrime n
  | n <= 3 = n == 2 || n == 3
  | even n = False
  | 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)]
-------------------------------------------------------------------------------
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 #-}

parse1 :: IO Int
parse1 = readLn
{-# INLINE parse1 #-}

parseN :: Int -> IO (VU.Vector Int)
parseN n = VU.replicateM n parse1
{-# INLINE parseN #-}
0