From 376a77de38a4b552200734bb3c721f0fd01dfc72 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Fri, 24 Feb 2017 11:01:57 +0100
Subject: Lot's of small changes to math chapter.

---
 math/phi.cpp | 11 +++++++----
 1 file changed, 7 insertions(+), 4 deletions(-)

(limited to 'math/phi.cpp')

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;
-- 
cgit v1.2.3