More than 5 years have passed since last update.
Haskell で「素数列」のリストを返す関数を作ってみました。
ベンチマークテスト代わりに、「Project Euler」の問題 10 を解いてみました。
追記
こちら で紹介していただいた際に、内部関数 f の第一引数 m が
m = 5
m = 5 * 5
m = 5 * 5 * 7
...
と変化していくことに気付きました。
この引数は素数を小さい順に１つずつ順番にかけていくべきなので、このままでは最初の５が余計です。
そこで
m = 1
m = 1 * 5
m = 1 * 5 * 7
...
となるように修正したものを挙げておきます。
性能的にはほとんど変わらないので、ただの自己満足ですが…（笑）
《 修正後バージョン 》
primes.hs
--
-- 素数列（修正版）
--
-- http://d.hatena.ne.jp/notogawa/20110114/1295006865 を参考に
-- gcd の使い方が秀逸
--
primes :: Integral a => [a]
primes = map fromIntegral $ [2, 3] ++ primes'
where
primes' = [5] ++ f 1 7 primes'
f m s (p : ps) = [n | n <- ns, gcd m n == 1] ++ f (m * p) (p * p) ps
where ns = [x + y | x <- [s, s + 6 .. p * p - 2], y <- [0, 4]]
《 修正前バージョン 》
p010.hs
-- 素数列
-- http://d.hatena.ne.jp/notogawa/20110114/1295006865 を参考に
-- gcd の使い方が秀逸
primes :: Integral a => [a]
primes = map fromIntegral primes'
where
primes' = [2, 3, 5] ++ f 5 7 (drop 2 primes')
f m s (p : ps) = [n | n <- ns, gcd m n == 1] ++ f (m * p) (p * p) ps
where ns = [x + y | x <- [s, s + 6 .. p * p - 2], y <- [0, 4]]
main :: IO ()
main = print $ sum $ takeWhile (< 2000000) primes
-- Intel Core i5 2.40GHz
--
-- >p010 +RTS -sstderr
-- p010 +RTS -sstderr
-- p010 +RTS -sstderr
-- 142913828922
-- 57,695,712 bytes allocated in the heap
-- 6,237,676 bytes copied during GC
-- 2,198,460 bytes maximum residency (3 sample(s))
-- 231,308 bytes maximum slop
-- 6 MB total memory in use (0 MB lost due to fragmentation)
-- Generation 0: 108 collections, 0 parallel, 0.02s, 0.01s elapsed
-- Generation 1: 3 collections, 0 parallel, 0.00s, 0.01s elapsed
-- INIT time 0.00s ( 0.00s elapsed)
-- MUT time 0.23s ( 0.23s elapsed)
-- GC time 0.02s ( 0.01s elapsed)
-- EXIT time 0.00s ( 0.00s elapsed)
-- Total time 0.25s ( 0.24s elapsed)
-- %GC time 6.2% (5.0% elapsed)
-- Alloc rate 246,561,818 bytes per MUT second
-- Productivity 93.8% of total user, 96.0% of total elapsed
Register as a new user and use Qiita more conveniently
- You get articles that match your needs
- You can efficiently read back useful information
- You can use dark theme