如何让这个 Haskell 程序运行得更快

Question

所以我一直在尝试通过解决 Codeforce 上的一些问题来学习 Haskell。
即使我认为我的时间复杂度是最佳的，我也得到了很多 TLE（超出时间限制）。

我的问题是：是我编写这个程序的方式使它变慢了吗？

例如，这里是问题。

基本上答案是找到给定的，其中 and =和之间的除数数之差。annan = 2*an-1 + D(n)D(n)nn-1

（更新：上限为n10 ⁶）。

下面是我的程序。

import qualified Data.Map.Strict as Map

main = do t <- read <$> getLine
          putStrLn . show $ solve t

solve :: Integer -> Integer
solve 0 = 1
solve 1 = 1
solve n = (2*(solve (n-1)) + (fact n) - (fact (n-1))) `mod` 998244353
    where fact n = foldl (\s -> \t -> s*(snd t + 1)) 1 (Map.toList . factorization  $ n)
    --the number of divisors of a number

--copied from Internet,infinite prime list
primes :: [Integer]
primes = 2: 3: sieve (tail primes) [5,7..]
  where
    sieve (p:ps) xs = h ++ sieve ps [x | x <- t, x `rem` p /= 0]
      where (h,~(_:t)) = span (< p*p) xs

--make factorization of a number
factorization :: Integer -> Map.Map Integer Integer
factorization 1 = Map.fromList []
factorization x = Map.insertWith (+) factor 1 (factorization (x `div` factor))
    where factor = head $ filter (\s -> (x `mod` s) == 0) ls
          ls = primes

该程序未能在时限内解决。

那么谁能指出我哪里做错了以及如何解决它？
或者在时间限制内使用 Haskell 解决这个问题是不可能的？

Answer 1

您的时间复杂度不是最优的有很多方式。最明显的是使用试除法而不是例如筛子的素数查找器。也许这很好，因为您只计算一次质数，但这并不能激发信心。

factorization也至少有一个明显的问题。考虑对像 78893012641 这样的数进行因式分解，其质数因式分解为 280879^2。您将搜索每个质数直至 280879：昂贵，但几乎不可避免。但是，此时您除以 280879，然后尝试对 280879 进行因式分解，从 2 开始并再次扫描所有小素数，即使您刚刚发现它们都不是因数！

正如 Li-yao Xia 在评论中所说，我也会怀疑非常大的Integers 在取模之前的乘法，而不是在每次乘法之后取模。