Adding Jojo's Miller-Rabin code to the document and improving prime sieve.

3 files changed, 30 insertions, 22 deletions

diff --git a/math/math.tex b/math/math.tex
index acc85f6..7093f78 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -17,16 +17,19 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$.
 \end{description}
 \lstinputlisting{math/multInv.cpp}
 
-\subsection{Primzahlsieb von Eratosthenes}
+\subsection{Primzahlsieb von \textsc{Eratosthenes}}
 \lstinputlisting{math/primeSieve.cpp}
 
-\subsubsection{Faktorisierung}
+\subsection{\textsc{Miller}-\textsc{Rabin}-Primzahltest}
+\lstinputlisting{math/millerRabin.cpp}
+
+\subsection{Faktorisierung}
 \lstinputlisting{math/factor.cpp}
 
-\subsubsection{Mod-Exponent über $\mathbb{F}_p$}
+\subsection{Mod-Exponent über $\mathbb{F}_p$}
 \lstinputlisting{math/modExp.cpp}
 
-\subsubsection{LGS über $\mathbb{F}_p$}
+\subsection{LGS über $\mathbb{F}_p$}
 \lstinputlisting{math/lgsFp.cpp}
 
 \subsection{Binomialkoeffizienten}
diff --git a/math/miller_rabin.cpp b/math/millerRabin.cpp
index ad8c163..d41f33a 100644
--- a/math/miller_rabin.cpp
+++ b/math/millerRabin.cpp
@@ -1,6 +1,6 @@
-//theoretical: n < 318,665,857,834,031,151,167,461 ( > 10^23)
-//but: n ~<= 10^18 (because of MAX(ll))
-//O(logn)
+// Theoretisch: n < 318,665,857,834,031,151,167,461 (> 10^23)
+// Praktisch: n <= 10^18 (long long)
+// Laufzeit: O(log n)
 bool isPrime(ll n) {
 	if(n == 2) return true;
 	if(n < 2 || n % 2 == 0) return false;
@@ -13,7 +13,6 @@ bool isPrime(ll n) {
 			v = mult_mod(v, v, n);
 			if(v == n-1 || v <= 1) break;
 		}
-		
 		if(v != n-1) return false;
 	}
 	return true;
diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp
index 183d742..4732d0a 100644
--- a/math/primeSieve.cpp
+++ b/math/primeSieve.cpp
@@ -1,15 +1,21 @@
-#define N 10000001
-vector<ll> primes;
-//Finds all prime numbers between 0..N
-//Use this method for N < 10000000 to avoid memory access errors
-void primeSieve() {
-  bitset<N> isPrime; isPrime.set();
-  isPrime[0] = isPrime[1] = 0;
-  for(ll i = 2; i < N+1; i+=2) {
-      if(isPrime[i]) {
-	      for(ll j = i*i; j >= 0 && j < N+1; j+=i) isPrime[j] = 0;
-	      primes.push_back(i);
-      }
-      if(i == 2) i--;
+// Sieb des Eratosthenes. Laufzeit: O(n * log log n)
+#define N 100000001 // Bis 10^8 in unter 64MB Speicher.
+bitset<N / 2> isPrime;
+
+inline bool check(int x) { // Diese Methode zum Lookup verwenden.
+  if (x < 2) return false;
+  else if (x == 2) return true;
+  else if (!(x & 1)) return false;
+  else return !isPrime[x / 2];
+}
+
+inline int primeSieve(int n) { // Gibt die Anzahl der Primzahlen <= n zurück.
+  int counter = 1;
+  for (int i = 3; i <= min(N, n); i += 2) {
+    if (!isPrime[i / 2]) {
+      for (int j = 3 * i; j <= min(N, n); j+= 2 * i) isPrime[j / 2] = 1;
+      counter++;
+    }
   }
-}
\ No newline at end of file
+  return counter;
+}