結果

問題 No.36 素数が嫌い！
コンテスト
ユーザー こまる
提出日時 2020-10-06 22:39:41
言語 Haskell
(9.10.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,312 bytes
コンパイル時間 151 ms
コンパイル使用メモリ 149,504 KB
最終ジャッジ日時 2024-11-14 23:51:12
合計ジャッジ時間 601 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、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:5: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.
  |
5 | import qualified GHC.Integer.GMP.Internals     as GMP
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

ソースコード

diff # 

{-# LANGUAGE BangPatterns #-}
import           Control.Monad
import           Data.Bool
import           Data.Bits
import qualified GHC.Integer.GMP.Internals     as GMP
import qualified Data.Array.ST                 as ArrST
import qualified Data.Array.Unboxed            as ArrU


thirdRoot :: Float -> Float
thirdRoot n = fst $ until (uncurry(==)) (\(_, x0) -> (x0,((n - 1.0) * x0 + 3.0 / x0 ** (n - 1.0)) / n)) (3.0, 3.0 / n)

sieveUA :: Int -> ArrU.UArray Int Bool
sieveUA top = ArrST.runSTUArray $ do
    let m = (top-1) `div` 2
        r = floor . sqrt $ fromIntegral top + 1
    sieve <- ArrST.newArray (1,m) True
    forM_ [1..r `div` 2] $ \i -> do
      isPrime <- ArrST.readArray sieve i
      when isPrime $ do
        forM_ [2*i*(i+1), 2*i*(i+2)+1..m] $ \j -> do
          ArrST.writeArray sieve j False
    return sieve

primesToUA :: Int -> [Int]
primesToUA top = 2 : [i*2+1 | (i,True) <- ArrU.assocs $ sieveUA top]

main :: IO ()
main = readLn >>= putStrLn . solver

solver :: Int -> String
solver n = bool "NO" "YES" $ func1 n

func1 :: Int -> Bool
func1 n = iter n 0 ps
  where
    ps = primesToUA 40000
    iter res p []
      | p >= 3 || (p == 2 && millerRabin p) = True
      | p == 1 = not $ millerRabin res
      | res >= 10 ^ 12 = let xxx = round $ thirdRoot $ fromIntegral res
                          in if even xxx then millerRabin $ xxx - 1 else millerRabin xxx
      | otherwise = False
    iter i j (l:ls)
      | i <  2         = j >= 3
      | j >= 3         = True
      | i `mod` l == 0 = iter (func2 i l) (j + func3 i l) ls
      | otherwise      = iter i j ls

func2 :: Int -> Int -> Int
func2 n mo
  | n `mod` mo == 0 = func2 (n `div` mo) mo
  | otherwise       = n

func3 :: Int -> Int -> Int
func3 n mo = iter n mo 0
  where
    iter i j k
      | i `mod` j == 0 = iter (i `div` j) j (k + 1)
      | otherwise      = k

millerRabin :: Int -> Bool
millerRabin k
  | k <= 3 = k == 2 || k == 3
  | even k = False
  | otherwise = mr k
  where
    mr :: Int -> Bool
    mr 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
        powModInt :: Int -> Int -> Int -> Int
        powModInt !a !n !mo = fI $ GMP.powModInteger (fi a) (fi n) (fi mo)
        !m = n - 1
        !s = ctz m
        !d = m .>>. s
        loop :: [Int] -> Bool
        loop [] = True
        loop (a:as)
          | powModInt a d n /= 1 && allok = False
          | otherwise = loop as
          where allok = all (\r -> (powModInt a ((1 .<<. r) * d) n) /= m) [0..(s - 1)]

infixl 8 .<<., .>>.
(.<<.) :: Bits b => b -> Int -> b
(.<<.) = unsafeShiftL
{-# INLINE (.<<.) #-}

(.>>.) :: Bits b => b -> Int -> b
(.>>.) = unsafeShiftR
{-# INLINE (.>>.) #-}

fi :: Int -> Integer
fi = fromIntegral
{-# INLINE fi #-}

fI :: Integer -> Int
fI = fromInteger
{-# INLINE fI #-}

ctz :: FiniteBits fb => fb -> Int
ctz = countTrailingZeros
{-# INLINE ctz #-}
0