Help us understand the problem. What is going on with this article?

Haskell で「素数列」をつくる。

More than 3 years have passed since last update.

Haskell で「素数列」のリストを返す関数を作ってみました。

ベンチマークテスト代わりに、「Project Euler」の問題 10 を解いてみました。

追記

こちら で紹介していただいた際に、内部関数 f の第一引数 m が

m = 5
m = 5 * 5
m = 5 * 5 * 7
...

と変化していくことに気付きました。

この引数は素数を小さい順に1つずつ順番にかけていくべきなので、このままでは最初の5が余計です。
そこで

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
little_Haskeller
好きなもの…Haskell, Scheme, Ruby
http://tsumuji.cocolog-nifty.com/tsumuji/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away