import Data.List
import Data.Maybe
-- 31
isqrt :: Int -> Int
isqrt = floor . sqrt . fromIntegral
isprime :: Int -> Bool
isprime n
| n <= 1 = False
| otherwise = foldr (\a b -> (rem n a /= 0 && b)) True [2..(isqrt n)]
-- 32
mygcd :: Int -> Int -> Int
mygcd a b
| a == 0 = b
| b == 0 = a
| a > b = mygcd b $ rem a b
| otherwise = mygcd a $ rem b a
-- 33
coprime :: Int -> Int -> Bool
coprime a b = mygcd a b == 1
-- 34
totient :: Int -> Int
totient n = length (filter (coprime n) [1..n])
-- 35
primeFactors :: Int -> [Int]
primeFactors n
| n == 1 = []
| factor n == [] = [n]
| otherwise = let f = head (factor n) in f : primeFactors (div n f)
factor :: Int -> [Int]
factor n = take 1 (filter (\x -> (mod n x) == 0) [2 .. (isqrt n)])
-- 36
primeFactorsMult :: Int -> [(Int, Int)]
primeFactorsMult n = map (\x -> (head x, length x)) $ group $ primeFactors n
-- 37
phi :: Int -> Int
phi n = foldr (\a b -> b*(fst a - 1)*((fst a)^(snd a - 1))) 1 $ primeFactorsMult n
-- 39
primesR :: Int -> Int -> [Int]
primesR a b = filter isprime [a .. b]
-- 40
goldbach :: Int -> (Int, Int)
goldbach n = (gb n, n-(gb n))
gb :: Int -> Int
gb n = fromJust $ find (\a -> elem (n-a) (primesR 2 n)) $ primesR 2 n
-- 41
goldbachList :: Int -> Int -> [(Int, Int)]
goldbachList a b
| a > b = []
| mod a 2 == 0 = goldbach a : goldbachList (a+2) b
| otherwise = goldbach (a+1) : goldbachList (a+3) b
goldbachList' :: Int -> Int -> Int -> [(Int, Int)]
goldbachList' a b c = filter (\x -> (fst x)>c) $ goldbachList a b