diff options
| -rw-r--r-- | math/primeSieve.cpp | 16 | ||||
| -rw-r--r-- | other/other.tex | 10 | ||||
| -rw-r--r-- | tcr.pdf | bin | 275404 -> 275989 bytes |
3 files changed, 18 insertions, 8 deletions
diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp index 37ea12c..656a597 100644 --- a/math/primeSieve.cpp +++ b/math/primeSieve.cpp @@ -1,19 +1,19 @@ // Laufzeit: O(n * log log n) -#define N 100000001 // Bis 10^8 in unter 64MB Speicher. -bitset<N / 2> isPrime; +#define N 100000000 // Bis 10^8 in unter 64MB Speicher. +bitset<N / 2> isNotPrime; 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]; + else return !isNotPrime[x / 2]; } -inline int primeSieve(int n) { // Rückgabe: Anzahl der Primzahlen <= n. - 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; +inline int primeSieve() { // Rückgabe: Anzahl der Primzahlen < N. + int counter = 1; // Die 2, die sonst vergessen würde. + for (int i = 3; i < N; i += 2) { + if (!isNotPrime[i / 2]) { + for (int j = 3 * i; j < N; j+= 2 * i) isNotPrime[j / 2] = 1; counter++; }} return counter; diff --git a/other/other.tex b/other/other.tex index 2ce8043..61f7a46 100644 --- a/other/other.tex +++ b/other/other.tex @@ -100,6 +100,16 @@ $n$ Personen im Kreis, jeder $k$-te wird erschossen. \item \textbf{Verteilung von Primzahlen:} Für alle $n \in \mathbb{N}$ gilt: Ex existiert eine Primzahl $p$ mit $n \leq p \leq 2n$. + + \item \textbf{Satz von \textsc{Kirchhoff}:} + Sei $G$ ein zusammenhängender, ungerichteter Graph evtl. mit Mehrfachkanten. + Sei $A$ die Adjazenzmatrix von $G$. + Dabei ist $a_{ij}$ die Anzahl der Kanten zwischen Knoten $i$ und $j$. + Sei $B$ eine Diagonalmatrix, $b_{ii}$ sei der Grad von Knoten $i$. + Definiere $R = B - A$. + Alle Kofaktoren von $R$ sind gleich und die Anzahl der Spannbäume von $G$. + \newline + Entferne letzte Zeile und Spalte und berechne Betrag der Determinante. \end{itemize} \subsection{Tipps \& Tricks} Binary files differ |