1 files changed, 20 insertions, 14 deletions
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;
+}