correct primeSieve and improve prime factorization

1 files changed, 15 insertions, 13 deletions

diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp
index db96e5b..183d742 100644
--- a/math/primeSieve.cpp
+++ b/math/primeSieve.cpp
@@ -1,13 +1,15 @@
-vector<int> primes;
-void primeSieve(ll n) { //berechnet die Primzahlen kleiner n
-	vector<int> isPrime(n,true);
-	for(ll i = 2; i < n; i+=2) {
-		if(isPrime[i]) {
-			primes.push_back(i);
-			if(i*i <= n) {
-				for(ll j = i; i*j < n; j+=2) isPrime[i*j] = false;
-			}
-		}
-		if(i == 2) i--;
-	}
-} 
+#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--;
+  }
+}
\ No newline at end of file