結果
問題 | No.308 素数は通れません |
ユーザー | こまる |
提出日時 | 2020-10-07 23:37:46 |
言語 | Haskell (9.8.2) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,005 bytes |
コンパイル時間 | 207 ms |
コンパイル使用メモリ | 150,400 KB |
最終ジャッジ日時 | 2024-04-27 05:01:35 |
合計ジャッジ時間 | 833 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、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:3: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. | 3 | import qualified GHC.Integer.GMP.Internals as GMP | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ソースコード
{-# LANGUAGE BangPatterns #-} import Data.Bits (Bits (unsafeShiftL, unsafeShiftR), FiniteBits (countTrailingZeros)) import qualified GHC.Integer.GMP.Internals as GMP main :: IO () main = do n <- readLn :: IO Integer if n < 50 then putStrLn $ ["0","1","2","3","3","5","5","7","7","7","7","11","11","13","13","7","7","17","8","19","19","19","7","23","23","23","8","8","8","29","8","31","8","8","8","8","8","37","8","8","8","41","8","43","8","8","8","47","8","14","8"] !! (fromInteger n) else if n `mod` 8 == 1 && isPrime (n - 8) then putStrLn "14" else putStrLn "8" 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 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 .>>. 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)] powModInt :: Int -> Int -> Int -> Int powModInt a n mo = fromInteger $ GMP.powModInteger (fromIntegral a) (fromIntegral n) (fromIntegral mo) {-# INLINE powModInt #-} infixl 8 .>>., .<<. (.>>.) :: Bits i => i -> Int -> i (.>>.) = unsafeShiftR {-# INLINE (.>>.) #-} (.<<.) :: Bits i => i -> Int -> i (.<<.) = unsafeShiftL {-# INLINE (.<<.) #-}