优化Haskell代码,计算低于200万的所有素数之和可以通过以下步骤实现:
以下是一个示例的Haskell代码实现:
import Data.Array.ST
import Data.Array.Unboxed
import Control.Monad.ST
-- 生成低于n的素数列表
sieve :: Int -> UArray Int Bool
sieve n = runSTUArray $ do
-- 使用位图表示数字是否为素数
isPrime <- newArray (2, n) True
let limit = floor (sqrt (fromIntegral n))
-- 从2开始遍历,将每个素数的倍数标记为非素数
forM_ [2..limit] $ \i -> do
prime <- readArray isPrime i
when prime $ do
forM_ [i*i, i*i+i..n] $ \j -> do
writeArray isPrime j False
return isPrime
-- 计算低于n的所有素数之和
sumOfPrimes :: Int -> Int
sumOfPrimes n = sum $ filter (isPrime !) [2..n]
where isPrime = sieve n
main :: IO ()
main = do
let n = 2000000
putStrLn $ "Sum of primes below " ++ show n ++ ": " ++ show (sumOfPrimes n)
这段代码使用了位图来表示数字是否为素数,以提高访问速度。它首先生成低于200万的素数列表,然后计算素数之和并输出结果。
推荐的腾讯云相关产品和产品介绍链接地址:
领取专属 10元无门槛券
手把手带您无忧上云