結果
問題 | No.308 素数は通れません |
ユーザー |
|
提出日時 | 2020-10-07 23:37:46 |
言語 | Haskell (9.10.1) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,005 bytes |
コンパイル時間 | 264 ms |
コンパイル使用メモリ | 150,144 KB |
最終ジャッジ日時 | 2024-11-15 05:01:24 |
合計ジャッジ時間 | 773 ms |
ジャッジサーバーID (参考情報) |
judge2 / 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: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 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ソースコード
LANGUAGEimportData.BitsBits,FiniteBitsimportqualifiedGHC.Integer.GMP.InternalsasGMPmain::IO()main = don <- readLn :: IO Integerif n < 50then 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->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 = m .>>. scheck3::Int->Boolcheck3 a = powModInt a d n /= 1INLINEcheck4::Int->Int->Boolcheck4 a i = (powModInt a (d * (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)INLINEinfixl 8 .>>., .<<.(.>>.)::Bitsi=>i->Int->i(.>>.) = unsafeShiftRINLINE(.<<.)::Bitsi=>i->Int->i(.<<.) = unsafeShiftLINLINE