약수와 소수

약수

divisors :: Int -> [Int]
divisors n = 
  [x | x <- [1..n `div` 2], n `rem` x == 0] ++ [n]

• 수학의 조건 제시법처럼 Haskell은 list comprehention을 이용해서 표현할 수 있다. 원래 자기 자신을 포함해서 조건을 제시해야 하지만, 약수의 성질을 이용해서 자신의 반수까지 약수를 구한 뒤 자기 자신을 추가해준다.

공약수

import Data.List

ommonDivisor :: Int -> Int -> [Int]
commonDivisor x y = divisors x `intersect` divisors y

• 두 수의 약수 집합의 교집합이 공약수. intersect 는 교집합을 구하는 원소. Data.List 모듈에 있다.

소수

isPrime :: Int -> Bool 
isPrime n = divisors n == [1,n]

primes :: Int -> [Int]
primes n = [x | x <- [2..n], isPrime x]