Personal tools

99 questions/Solutions/34

From HaskellWiki

< 99 questions | Solutions(Difference between revisions)
Jump to: navigation, search
 
m
Line 10: Line 10:
   
 
We take coprime from the previous exercise and give it to filter, which applies it to each element of a list from 1 to one less than the number, returning only those that are true. length tells us how many elements are in the resulting list, and thus how many elements are coprime to n
 
We take coprime from the previous exercise and give it to filter, which applies it to each element of a list from 1 to one less than the number, returning only those that are true. length tells us how many elements are in the resulting list, and thus how many elements are coprime to n
  +
  +
Or slightly more concise, using list comprehension:
  +
<haskell>
  +
totient n = length [x | x <- [1..n], coprime x n]
  +
</haskell>

Revision as of 20:50, 19 January 2011

(**) Calculate Euler's totient function phi(m).

Euler's so-called totient function phi(m) is defined as the number of positive integers r (1 <= r < m) that are coprime to m.

totient 1 = 1
totient a = length $ filter (coprime a) [1..a-1]
 where coprime a b = gcd a b == 1

We take coprime from the previous exercise and give it to filter, which applies it to each element of a list from 1 to one less than the number, returning only those that are true. length tells us how many elements are in the resulting list, and thus how many elements are coprime to n

Or slightly more concise, using list comprehension:

totient n = length [x | x <- [1..n], coprime x n]