kotapiku
11/21/2017 - 10:01 AM

99haskell

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