Hatena::Grouphaskell

Haskellで遊ぶよ

 | 

2009-06-26

4つの異なる素数を因数に持つ数が4つ続くところを見つける

08:10

説明は面倒なのでリンク先を見てもらうとする。


import List

factors :: Integer -> [Integer]
factors n = f n (2:[3,5..])
  where
    f n (m:ms) | n <= 1         = []
               | n < m * m      = [n]
               | n `mod` m == 0 = m:f (n `div` m) (m:ms)
               | otherwise      = f n ms

dpf n = (==n) . length . nub . factors

conseq n xs = conseq' xs []
    where
        conseq' (x:xs') [] = conseq' xs' [x]
        conseq' (x:xs') ys@(y:_) = if length ys == n
                                   then reverse ys
                                   else if x == y + 1
                                        then conseq' xs' (x:ys)
                                        else conseq' xs' [x]

main = print $ conseq 4 $ filter (dpf 4) [2..]

自然数を素因数分解する関数 factors は昨日の続きでこちらから拝借。

素因数分解するのに素数のリストを求めるのは、割り算が無駄に増えるだけで効率が悪い、と言われてみればその通りだけど思いつかなかった。

トラックバック - http://haskell.g.hatena.ne.jp/edvakf/20090626
 |