add Euler's Totient function (keon#421)

goswami-rahul · keon · commit 62a3ba2b0be4 · 2018-10-07T20:09:06.000-07:00
* add Euler's Totient function

* add link to Euler's totient function in README
diff --git a/README.md b/README.md
@@ -186,6 +186,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [base_conversion](algorithms/maths/base_conversion.py)
     - [combination](algorithms/maths/combination.py)
     - [decimal_to_binary_ip](algorithms/maths/decimal_to_binary_ip.py)
+    - [euler_totient](algorithms/maths/euler_totient.py)
     - [extended_gcd](algorithms/maths/extended_gcd.py)
     - [factorial](algorithms/maths/factorial.py)    
     - [gcd/lcm](algorithms/maths/gcd.py)
diff --git a/algorithms/maths/__init__.py b/algorithms/maths/__init__.py
@@ -1,5 +1,6 @@
 from .base_conversion import *
 from .decimal_to_binary_ip import *
+from .euler_totient import *
 from .extended_gcd import *
 from .factorial import *
 from .gcd import *
diff --git a/algorithms/maths/euler_totient.py b/algorithms/maths/euler_totient.py
@@ -0,0 +1,18 @@
+"""
+Euler's totient function, also known as phi-function ϕ(n),
+counts the number of integers between 1 and n inclusive,
+which are coprime to n.
+(Two numbers are coprime if their greatest common divisor (GCD) equals 1).
+"""
+def euler_totient(n):
+    """Euler's totient function or Phi function.
+    Time Complexity: O(sqrt(n))."""
+    result = n;
+    for i in range(2, int(n ** 0.5) + 1):
+        if n % i == 0:
+            while n % i == 0:
+                n //= i
+            result -= result // i
+    if n > 1:
+        result -= result // n;
+    return result;
diff --git a/tests/test_maths.py b/tests/test_maths.py
@@ -1,6 +1,7 @@
 from algorithms.maths import (
     int_to_base, base_to_int,
     decimal_to_binary_ip,
+    euler_totient,
     extended_gcd,
     factorial, factorial_recur,
     gcd, lcm,
@@ -36,8 +37,8 @@ def test_base_to_int(self):
         self.assertEqual(5, base_to_int("101", 2))
         self.assertEqual(0, base_to_int("0", 2))
         self.assertEqual(255, base_to_int("FF", 16))
-        
-        
+
+
 class TestDecimalToBinaryIP(unittest.TestCase):
     """
     Test for the file decimal_to_binary_ip.py
@@ -55,6 +56,21 @@ def test_decimal_to_binary_ip(self):
                          decimal_to_binary_ip("192.168.0.1"))
 
 
+class TestEulerTotient(unittest.TestCase):
+    """[summary]
+    Test for the file euler_totient.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_euler_totient(self):
+        self.assertEqual(4, euler_totient(8))
+        self.assertEqual(12, euler_totient(21))
+        self.assertEqual(311040, euler_totient(674614))
+        self.assertEqual(2354352, euler_totient(3435145))
+
+
 class TestExtendedGcd(unittest.TestCase):
     """[summary]
     Test for the file extended_gcd.py
@@ -274,4 +290,3 @@ def test_factorial_recur(self):
 
 if __name__ == "__main__":
     unittest.main()
-
