Haskell 99問 (31-41)

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
[PR]
by tnomura9 | 2009-08-14 08:13 | Haskell | Comments(0)
<< Haskell 99問 (46... Haskell 99問 (21... >>