Haskell 99問 (31-41) 算術
http://www.haskell.org/haskellwiki/99_questions/31_to_41 問題31 引数が素数かどうかを判別する関数を作れ。 実行例 P31> isPrime 7 True 解答 isPrime :: Integral a => a -> Bool isPrime p = p > 1 && (all (\n -> p `mod` n /= 0 ) $ takeWhile (\n -> n*n <= p) [2..]) 問題32 最小公倍数を求める関数を作れ。 実行例 Main> [myGCD 36 63, myGCD (-3) (-6), myGCD (-3) 6] [9,3,3] 解答 (ユークリッドの互除法を使う。最大公約数の関数は標準で gcd がある。) myGCD :: Integer -> Integer -> Integer myGCD a b | b == 0 = abs a | otherwise = myGCD b (a `mod` b) 問題33 二つの引数が互いに素かどうかを判別する関数を作れ。 実行例 * coprime 35 64 True 解答 coprime a b = gcd a b == 1 問題34 オイラーの totient function phi(m) を作れ。[1..n]のうちで n と互いに素になる数の数を返す関数。 実行例 * totient 10 4 解答 totient 1 = 1 totient a = length $ filter (coprime a) [1..a-1] where coprime a b = gcd a b == 1 問題35 引数の約数を求め昇順に表示する関数を求めよ。 実行例 > primeFactors 315 [3, 3, 5, 7] 解答 問題36 引数を素因数分解する関数を求めよ。重複する約数は同時に個数も示せ。 実行例 *Main> prime_factors_mult 315 [(3,2),(5,1),(7,1)] 解答 import List(group) prime_factors_mult n = encode $ primeFactors n primeFactors n = primeFactors' n 2 where primeFactors' n factor | factor*factor > n = [n] | n `mod` factor == 0 = factor : primeFactors' (n `div` factor) factor | otherwise = primeFactors' n (factor + 1) encode xs = map (\ys -> (head ys, length ys)) $ group xs 問題37 オイラーの totient function phi(m) を求めよ。問題34で求めた totient 関数は、問題36のように約数の個数が分かっていれば以下のように計算することができる。 phi(m) = (p1 - 1) * p1 ** (m1 - 1) + (p2 - 1) * p2 ** (m2 - 1) + (p3 - 1) * p3 ** (m3 - 1) + ... 解答 import List(group) totient m = product [(p - 1) * p ^ (c - 1) | (p, c) <- prime_factors_mult m] prime_factors_mult n = encode $ primeFactors n primeFactors n = primeFactors' n 2 where primeFactors' n factor | factor*factor > n = [n] | n `mod` factor == 0 = factor : primeFactors' (n `div` factor) factor | otherwise = primeFactors' n (factor + 1) encode xs = map (\ys -> (head ys, length ys)) $ group xs 問題38 問題34と問題37の totient 関数の求めかたのアルゴリズムの比較をせよ。 解答 なし。(例えば totient 10090 を計算させる) 問題39 引数で与えた範囲の整数の素数のリストを作れ。 実行例 P39> primesR 10 20 [11,13,17,19] 解答 primesR :: Integral a => a -> a -> [a] primesR a b = filter isPrime [a..b] isPrime :: Integral a => a -> Bool isPrime p = p > 1 && (all (\n -> p `mod` n /= 0 ) $ takeWhile (\n -> n*n <= p) [2..]) 別解 primesR :: Int -> Int -> [Int] primesR m n = takeWhile (<= n) $ dropWhile (< m) primes primes :: [Int] primes = sieve [2..] sieve :: [Int] -> [Int] sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0] 問題40 ゴールドバッハの予想を検証せよ。ゴールドバッハの予想とは2以上の偶数は必ず二つの素数の和になると言うことである。例 28 = 5 + 23 実行例 *goldbach 28 (5, 23) 解答 goldbach a = head $ filter (\e -> (isPrime $ fst e) && (isPrime $ snd e)) $ map (\e -> (e, a - e)) [1,3..div a 2] where factors a = filter (isFactor a) [2..a-1] isFactor a b = rem a b == 0 isPrime a = (length $ factors a) == 0 問題41 引数で指定した範囲の偶数のゴールドバッハ予想のリストを作れ。 実行例 *Exercises> goldbachList 9 20 [(3,7),(5,7),(3,11),(3,13),(5,13),(3,17)] 解答 goldbachList lb ub = map goldbach $ [even_lb,even_lb+2..ub] where even_lb = max ((lb+1) `div` 2 * 2) 4 goldbachList' lb ub mv = filter (\(a,b) -> a > mv && b > mv) $ goldbachList lb ub goldbach a = head $ filter (\e -> (isPrime $ fst e) && (isPrime $ snd e)) $ map (\e -> (e, a - e)) [1,3..div a 2] where factors a = filter (isFactor a) [2..a-1] isFactor a b = rem a b == 0 isPrime a = (length $ factors a) == 0
by tnomura9
| 2009-08-14 08:13
| Haskell
|
Comments(0)
|
カテゴリ
新型コロナウイルス 主インデックス Haskell 記事リスト 圏論記事リスト 考えるということのリスト 考えるということ ラッセルのパラドックス Haskell Prelude Ocaml ボーカロイド 圏論 jQuery デモ HTML Python ツールボックス XAMPP Ruby ubuntu WordPress 脳の話 話のネタ リンク 幸福論 キリスト教 心の話 メモ 電子カルテ Dojo JavaScript C# NetWalker ed と sed HTML Raspberry Pi C 言語 命題論理 以前の記事
最新のトラックバック
最新のコメント
ファン
記事ランキング
ブログジャンル
画像一覧
|
ファン申請 |
||