From 0545e74aeab679ff67e95b62f788a79d6a31f222 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Sun, 14 Feb 2016 00:36:49 +0100
Subject: Adding Jojo's Miller-Rabin code to the document and improving prime
 sieve.

---
 math/math.tex         | 11 +++++++----
 math/millerRabin.cpp  | 19 +++++++++++++++++++
 math/miller_rabin.cpp | 20 --------------------
 math/primeSieve.cpp   | 34 ++++++++++++++++++++--------------
 4 files changed, 46 insertions(+), 38 deletions(-)
 create mode 100644 math/millerRabin.cpp
 delete mode 100644 math/miller_rabin.cpp

(limited to 'math')

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/millerRabin.cpp b/math/millerRabin.cpp
new file mode 100644
index 0000000..d41f33a
--- /dev/null
+++ b/math/millerRabin.cpp
@@ -0,0 +1,19 @@
+// 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;
+	ll d=n-1,j=0;
+	while(d % 2 == 0) d >>= 1, j++;
+	for(int a = 2; a <= min((ll)37, n-1); a++) {
+		ll v = pow_mod(a, d, n);
+		if(v == 1 || v == n-1) continue;
+		for(int i = 1;  i <= j; i++) {
+			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/miller_rabin.cpp b/math/miller_rabin.cpp
deleted file mode 100644
index ad8c163..0000000
--- a/math/miller_rabin.cpp
+++ /dev/null
@@ -1,20 +0,0 @@
-//theoretical: n < 318,665,857,834,031,151,167,461 ( > 10^23)
-//but: n ~<= 10^18 (because of MAX(ll))
-//O(logn)
-bool isPrime(ll n) {
-	if(n == 2) return true;
-	if(n < 2 || n % 2 == 0) return false;
-	ll d=n-1,j=0;
-	while(d % 2 == 0) d >>= 1, j++;
-	for(int a = 2; a <= min((ll)37, n-1); a++) {
-		ll v = pow_mod(a, d, n);
-		if(v == 1 || v == n-1) continue;
-		for(int i = 1;  i <= j; i++) {
-			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;
+}
-- 
cgit v1.2.3