結果
問題 | No.308 素数は通れません |
ユーザー | かりあげクン |
提出日時 | 2020-09-30 10:23:48 |
言語 | Haskell (9.8.2) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 4,123 bytes |
コンパイル時間 | 296 ms |
コンパイル使用メモリ | 155,512 KB |
最終ジャッジ日時 | 2024-04-27 05:01:33 |
合計ジャッジ時間 | 1,148 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、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: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 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ソースコード
{-# 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 Integer if n < 50 then print $ [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 print 14 else print 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 = 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)] powModInt :: Int -> Int -> Int -> Int powModInt a n mo = fromInteger $ GMP.powModInteger (fromIntegral a) (fromIntegral n) (fromIntegral mo) {-# INLINE powModInt #-} ------------------------------------------------------------------------------- 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 ------------------------------------------------------------------------------- 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 (.<<.) #-}