結果

問題 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言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
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
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

ソースコード

diff #
プレゼンテーションモードにする

{-# 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 (.<<.) #-}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0