5
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

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

Last updated at Posted at 2012-12-26

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
5
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
5
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?