From 31588dc1212d353adb58fbffd207b60b4868b23f Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Sun, 22 Oct 2017 19:53:16 +0200
Subject: Adding sieve implementation for Euler's Totient function.

---
 math/phi.cpp | 8 ++++++++
 1 file changed, 8 insertions(+)

(limited to 'math/phi.cpp')

diff --git a/math/phi.cpp b/math/phi.cpp
index 492a9d2..f568bba 100644
--- a/math/phi.cpp
+++ b/math/phi.cpp
@@ -10,3 +10,11 @@ ll phi(ll n) { // Laufzeit: O(sqrt(n))
   if(n > 1) result -= result / n;
   return result;
 }
+
+// Sieb, falls alle Werte benötigt werden. Laufzeit: O(N*log(log(N)))
+for (int i = 1; i <= N; i++) phi[i] = i;
+for (int i = 2; i <= N; i++) if (phi[i] == i) {
+  for (int j = i; j <= N; j += i) {
+    phi[j] /= i;
+    phi[j] *= i - 1;
+}}
-- 
cgit v1.2.3