Использование величайшего веселья общего делителя

Question

euclid :: Int -> Int евклид n = длина (фильтр (gcd n == 1) [1 .. n-1])

gcd :: Int -> Int -> Int

..

Answer 1

Ваша ошибка исходит от "gcd x 0 = x". «X :: Int» является выводимым результатом, но объявление типа «gcd :: Int-> Int-> Bool» ожидает Bool. Я ожидаю, что "gcd x 0 = (x == 1)" - это то, что вы должны были набрать.

Answer 2

Предполагая, что вы ищете Сложную функцию Эйлера , просто вызовите

euler_fi1 n = length $ filter ((==1).(gcd n)) [1..n-1]

В связанной статье WP приведена формула для непосредственного расчета:

euler_fi n = let 
   fs = Data.List.nub $ factorize n 
   pr = n * product [p-1 | p <- fs] 
  in Data.List.foldl' div pr fs

Для этого вам понадобится factorize функция:

factorize n | n > 1 = go n (2:[3,5..])  where
  go n ds@(d:t)
    | d*d > n    = [n]
    | r == 0     =  d : go q ds
    | otherwise  =      go n t
        where 
          (q,r)  = quotRem n d

Следующая оптимизация - использовать список простых чисел вместо (2:[3,5..]).