updated tcr

1 files changed, 17 insertions, 16 deletions

diff --git a/math/phi.cpp b/math/phi.cpp
index f568bba..482a139 100644
--- a/math/phi.cpp
+++ b/math/phi.cpp
@@ -1,20 +1,21 @@
 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) {  // Optimierung: Nur über Primzahlen iterieren.
-      while(n % i == 0)n /= i;
-      result -= result / i;
-    }
-  }
-  if(n > 1) result -= result / n;
-  return result;
+	// Optimierung: Falls n prim, n - 1 zurückgeben
+	ll result = n;
+	for(ll i = 2; i * i <= n; ++i) {
+		if(n % i == 0) {	// Optimierung: Nur Primzahlen
+			while(n % i == 0) n /= i;
+			result -= result / i;
+	}}
+	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;
+// Sieb, falls alle Werte benötigt werden.
+// Laufzeit: O(N*log(log(N)))
+vector<ll> phi(n + 1);
+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;
 }}