correct primeSieve and improve prime factorization

3 files changed, 35 insertions, 32 deletions

diff --git a/math/factor.cpp b/math/factor.cpp
index 0cbca33..621d057 100644
--- a/math/factor.cpp
+++ b/math/factor.cpp
@@ -1,19 +1,20 @@
-const ll PRIME_SIZE = 10000000;
-vector<int> primes; //call primeSieve(PRIME_SIZE); before
-
-//Factorize the number n
-vector<int> factorize(ll n) {
-	vector<int> factor;
-	ll num = n;
-	int pos = 0;
-	while(num != 1)  {
-		if(num % primes[pos] == 0) {
-			num /= primes[pos];
-			factor.push_back(primes[pos]);
-		}
-		else pos++;
-		if(primes[pos]*primes[pos] > num) break;
-	}
-	if(num != 1) factor.push_back(num);
-	return factor;
-}
+typedef pair<int,int> ii;
+//Factorize a number n in its prime factors
+//Call primeSieve-method before with N > sqrt(n)
+//Return: Returns a vector of pairs, where the first entry in the pair is
+//the prime factor p and the second counts how many times p divides n
+vector<ii> factorize(ll n) {
+  vector<ii> fact; ll num = n, i = 0, c = 0;
+  while(num != 1) {
+    if(num % primes[i] == 0) {
+      c++; num /= primes[i];
+    } else {
+      if(c > 0)
+	      fact.push_back(make_pair(primes[i],c));
+      i++; c = 0;
+      if(primes[i]*primes[i] > num) break;
+    }
+  }
+  if(num != 1) fact.push_back(make_pair(num,c+1));
+  return fact;
+}
\ No newline at end of file
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
diff --git a/tcr.pdf b/tcr.pdf
index 616bebc..b3a1c41 100644
--- a/tcr.pdf
+++ b/tcr.pdf