Repository: keon/algorithms
Pull request #421 (2018-10-03 21:34:51)

add Euler's Totient function
(Put an `X` inside the `[ ]` to denote check mark `[X]`.)


- [x] **If creating a new file :**
  - [x] added links to it in the README files ?
  - [x] included tests with it ?
  - [x] added description (overview of algorithm, time and space compleixty, and possible edge case) in docstrings ?

- [ ] **if done some changes :**
  - [ ] wrote short description in the PR explaining what the changes do ?
  - [ ] Fixes #[issue number] if related to any issue

- [ ] **other**


coveralls: ## Pull Request Test Coverage Report for [Build 765](https://coveralls.io/builds/19335723)

* **16** of **16**   **(100.0%)**  changed or added relevant lines in **2** files are covered.
* No unchanged relevant lines lost coverage.
* Overall coverage increased (+**0.08%**) to **71.637%**

---



|  Totals | [![Coverage Status](https://coveralls.io/builds/19335723/badge)](https://coveralls.io/builds/19335723) |
| :-- | --: |
| Change from base [Build 764](https://coveralls.io/builds/19318762): |  0.08% |
| Covered Lines: | 4324 |
| Relevant Lines: | 6036 |

---
##### 💛  - [Coveralls](https://coveralls.io)


Patch:
diff --git a/README.md b/README.md
index 6d5b747..aecd53b 100644
--- 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
index 177fed3..7a3fb7b 100644
--- 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
new file mode 100644
index 0000000..047b728
--- /dev/null
+++ 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;


Test patch:
diff --git a/tests/test_maths.py b/tests/test_maths.py
index 2499a4f..0777f9a 100644
--- 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 @@ class TestBaseConversion(unittest.TestCase):
         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 @@ class TestDecimalToBinaryIP(unittest.TestCase):
                          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 @@ class TestFactorial(unittest.TestCase):
 
 if __name__ == "__main__":
     unittest.main()
-