Commits

etorreborre  committed b3d0b16

improve totient

  • Participants
  • Parent commits 7f3dff8

Comments (0)

Files changed (2)

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: