Fast factorization method and Euler's phi function

1 files changed, 9 insertions, 0 deletions

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;
+}