1 files changed, 7 insertions, 4 deletions
diff --git a/math/phi.cpp b/math/phi.cpp
index c8f8900..492a9d2 100644
--- a/math/phi.cpp
+++ b/math/phi.cpp
@@ -1,8 +1,11 @@
-ll phi(ll n) {
+ll phi(ll n) { // Laufzeit: O(sqrt(n))
+  // Optimierung: Falls n prim, n - 1 zurückgeben (Miller-Rabin/Sieb).
   ll result = n;
-  for(int i = 2; i * i <= n; ++i) if(n % i == 0) {
-    while(n % i == 0)n /= i;
-    result -= result / i;
+  for(int i = 2; i * i <= n; ++i) {
+    if(n % i == 0) {  // Optimierung: Nur über Primzahlen iterieren.
+      while(n % i == 0)n /= i;
+      result -= result / i;
+    }
   }
   if(n > 1) result -= result / n;
   return result;