From 53c8e56d8b0ee3b4374ab90630673b971ddf2710 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Sat, 15 Oct 2016 22:48:49 +0200
Subject: Fast factorization method and Euler's phi function

---
 math/phi.cpp | 9 +++++++++
 1 file changed, 9 insertions(+)
 create mode 100644 math/phi.cpp

(limited to 'math/phi.cpp')

diff --git a/math/phi.cpp b/math/phi.cpp
new file mode 100644
index 0000000..c8f8900
--- /dev/null
+++ b/math/phi.cpp
@@ -0,0 +1,9 @@
+ll phi(ll n) {
+  ll result = n;
+  for(int i = 2; i * i <= n; ++i) if(n % i == 0) {
+    while(n % i == 0)n /= i;
+    result -= result / i;
+  }
+  if(n > 1) result -= result / n;
+  return result;
+}
-- 
cgit v1.2.3