使用最大公約數樂趣

Question

歐幾里得:: INT - >內部 歐幾里得N =長度（濾波器（GCD n ==可1）[1 ... N-1]）

GCD :: INT - >內部 - >詮釋

..

Answer 1

假設你正在尋找Euler's totient function，只需撥打

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..])。

Answer 2

您的錯誤來自「gcd x 0 = x」。 「x :: Int」是推斷的結果，但「gcd :: Int-> Int-> Bool」的類型聲明需要Bool。我預計「gcd x 0 =（x == 1）」是你應該輸入的內容。