結果
問題 | No.308 素数は通れません |
ユーザー |
![]() |
提出日時 | 2020-09-30 10:23:48 |
言語 | Haskell (9.10.1) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 4,123 bytes |
コンパイル時間 | 423 ms |
コンパイル使用メモリ | 151,424 KB |
最終ジャッジ日時 | 2024-11-15 05:01:09 |
合計ジャッジ時間 | 1,392 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、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 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ソースコード
LANGUAGEimportqualifiedControl.ArrowasArrowimportData.BitsBits,FiniteBitsimportData.BoolboolimportqualifiedData.ByteString.CharasBSCimportqualifiedData.ListasListimportqualifiedData.Vector.Fusion.Stream.MonadicasMSimportqualifiedData.Vector.UnboxedasVUimportqualifiedGHC.Integer.GMP.InternalsasGMPmain::IO()main = don <- readLn :: IO Integerif n < 50then 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 14else print 8isPrime::Integer->BoolisPrime k| k <= 3 = k == 2 || k == 3| even k = False| otherwise = millerRabin kwheremillerRabin::Integer->BoolmillerRabin 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 .>>. scTZ::Integer->Int->IntcTZ !i !cnt| odd i = cnt| otherwise = cTZ (i .>>. 1) (cnt + 1)INLINEcheck1::Integer->Boolcheck1 a = GMP.powModInteger a d n /= 1INLINEcheck2::Integer->Int->Boolcheck2 a i = (GMP.powModInteger a (d * (1 .<<. i)) n) /= mINLINEloop [] = Trueloop (a:as)| check1 a && allok = False| otherwise = loop aswhereallok = all (check2 a) [0..(s - 1)]millerRabinSmall::Int->BoolmillerRabinSmall 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 scheck3::Int->Boolcheck3 a = powModInt a d n /= 1INLINEcheck4::Int->Int->Boolcheck4 a i = (powModInt a (d * (unsafeShiftL 1 i)) n) /= mINLINEloop [] = Trueloop (a:as)| check3 a && allok = False| otherwise = loop aswhereallok = all (check4 a) [0..(s - 1)]powModInt::Int->Int->Int->IntpowModInt a n mo = fromInteger $ GMP.powModInteger (fromIntegral a) (fromIntegral n) (fromIntegral mo)INLINE-------------------------------------------------------------------------------type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString)parseInt::ParserIntparseInt = fmap (Arrow.second BSC8.tail) . BSC8.readIntparse1::IOIntparse1 = readLnparseN::Int->IOVUVectorIntparseN n = VU.replicateM n parse1-------------------------------------------------------------------------------rep::Monadm=>Int->Int->m()->m()rep n = flip MS.mapM_ (stream 0 n)INLINEstream::Monadm=>Int->Int->MSStreammIntstream !l !r = MS.Stream step lwherestep x| x < r = return $ MS.Yield x (x + 1)| otherwise = return MS.DoneINLINEINLINEinfixl 8 .>>., .<<.(.>>.)::Bitsi=>i->Int->i(.>>.) = unsafeShiftRINLINE(.<<.)::Bitsi=>i->Int->i(.<<.) = unsafeShiftLINLINE