# Commits

committed b3d0b16

improve totient

• Participants
• Parent commits 7f3dff8

# File src/main/scala/s99/ArithmeticSolutions.scala

`       n == 1 || n == 2 || !(2 to n/2).exists(isDivisor)`
` `
`     def isCoprimeTo(other: Int): Boolean = gcd(n, other) == 1`
`+`
`     def totient: Int = (1 to n).filter(_.isCoprimeTo(n)).size`
`-    def improvedTotient: Int = ???`
`+`
`+    def improvedTotient: Int = primeFactorMultiplicity.foldLeft(1) { (res, cur) =>`
`+      val (prime, number) = cur`
`+      res * (prime - 1) * math.pow(prime, (number - 1)).toInt`
`+    }`
` `
`     def primeFactors: List[Int] =`
`       if (n <= 1)      Nil`

# File src/test/scala/s99/ArithmeticSpec.scala

` `
`   """ Calculate Euler's totient function phi(m) (improved)`
`   See problem P34 for the definition of Euler's totient function. If the list of the prime factors of a number m is`
`-  known in the form of problem P36 then the function phi(m>) can be efficiently calculated as follows:`
`+  known in the form of problem P36 then the function phi(m>1) can be efficiently calculated as follows:`
`   Let [[p1, m1], [p2, m2], [p3, m3], ...] be the list of prime factors (and their multiplicities) of a given number m.`
`   Then phi(m) can be calculated with the following formula:`
` `